Calculating the jump constants for 32 prngs like xoshiro128++

87 views
Skip to first unread message

Johan Lundberg

unread,
Mar 17, 2020, 2:06:40 PM3/17/20
to prng
Hi All.
A few years ago I needed to generate the full jump tables for (from 2**0 to 2**127) for use with
the 64 bit xororoshiro128+. And not just the 2**64 (stream) jump available in the reference implementation.

Now, I'm porting code to GPU and need a 32 bit version of these tables for use with xoshiro128++/xoshiro128**

When I did them for xoroshiro128+ a few years ago I did it like below, but I'm not sure where to start with the 32 bit versions.
Can anyone help me out?

To be completely clear: I would like the full table, not only the 2**64 and 2**96 jumps available in the reference source:

static const uint32_t JUMP[] = { 0x8764000b, 0xf542d2d3, 0x6fa035c3, 0x77f2db5b }; //2**64
static const uint32_t LONG_JUMP[] = { 0xb523952e, 0x0b6f099f, 0xccf5a0ef, 0x1c580662 }; //2**96

We use full tables for two things:
1. to prove to ourselves that the stream mechanism "works" by jumping smaller steps (such as 2**6) which can be reproduced by repeatedly drawing numbers, and then similarly, that repetitions of smaller jumps are equivalent to larger jumps.
2. to provide faster stream jumping we combine 2**64, 2**66, 2**68 and so on to our needs. (In my timing tests back then a 'stride' of 2 like that was optimal or close to optimal). When I did this, LONG_JUMP was not implemented.

 best regards, Johan

What I did for the 64 bit version:

wget http://xoroshiro.di.unimi.it/xorshift-1.2.tgz  // is there an archive like this containing the 32 bit versions?
wget http://home.bway.net/lewis/fermat64/ferl64.tar.gz

 ... extact and build .

and
cd build_tmp/xorshiftbuild/xorshift-1.2/full/128roshiro64

j=0
while [[ $j -le 128 ]] ; do
    echo -e -n $j "   "|head -c4;  grep 55-14-36 prim.txt | ../common/jump.sh $j
    j=$((j+2))
done


Sebastiano Vigna

unread,
Mar 17, 2020, 2:11:26 PM3/17/20
to pr...@googlegroups.com


> On 17 Mar 2020, at 19:06, Johan Lundberg <lund...@gmail.com> wrote:
>
>
> What I did for the 64 bit version:
>
> wget http://xoroshiro.di.unimi.it/xorshift-1.2.tgz // is there an archive like this containing the 32 bit versions?
> wget http://home.bway.net/lewis/fermat64/ferl64.tar.gz
>
> ... extact and build .
>
> and
> cd build_tmp/xorshiftbuild/xorshift-1.2/full/128roshiro64
>
> j=0
> while [[ $j -le 128 ]] ; do
> echo -e -n $j " "|head -c4; grep 55-14-36 prim.txt | ../common/jump.sh $j
> j=$((j+2))
> done

OK. There's a bunch of scripts with "32", like "jump32.sh", etc., that I never uploaded. I'll do a quick tar and I'll send it to you--the same strategy will work for 32 bits.

Ciao,

seba

Oj002

unread,
Oct 8, 2020, 6:02:18 PM10/8/20
to prng
It would be nice to have those public.
I've been able to generate the constants for xoroshiro128, but I wasn't able to generate any other using http://xoroshiro.di.unimi.it/xorshift-1.2.tgz.
I'm not 100% confidant that they are correct, but here they are:
static const uint64_t prng_xoroshiro128Jump2Pow[128][2] = {
    { 0, 0 }, /* 0 -- 24-16-37 */
    { 0, 0 }, /* 1 -- 24-16-37 */
    { 0, 0 }, /* 2 -- 24-16-37 */
    { 0, 0 }, /* 3 -- 24-16-37 */
    { 0, 0 }, /* 4 -- 24-16-37 */
    { 0, 0 }, /* 5 -- 24-16-37 */
    { 0, 0 }, /* 6 -- 24-16-37 */
    { 0x095B8F76579AA001, 0x0008828E513B43D5 }, /* 7 -- 24-16-37 */
    { 0x162AD6EC01B26EAE, 0x7A8FF5B1C465A931 }, /* 8 -- 24-16-37 */
    { 0xB4FBAA5C54EE8B8F, 0xB18B0D36CD81A8F5 }, /* 9 -- 24-16-37 */
    { 0x1207A1706BEBB202, 0x23AC5E0BA1CECB29 }, /* 10 -- 24-16-37 */
    { 0x2C88EF71166BC53D, 0xBB18E9C8D463BB1B }, /* 11 -- 24-16-37 */
    { 0xC3865BB154E9BE10, 0xE3FBE606EF4E8E09 }, /* 12 -- 24-16-37 */
    { 0x1A9FC99FA7818274, 0x28FAAAEBB31EE2DB }, /* 13 -- 24-16-37 */
    { 0x588ABD4C2CE2BA80, 0x30A7C4EEF203C7EB }, /* 14 -- 24-16-37 */
    { 0x9C90DEBC053E8CEF, 0xA425003F3220A91D }, /* 15 -- 24-16-37 */
    { 0xB82CA99A09A4E71E, 0x81E1DD96586CF985 }, /* 16 -- 24-16-37 */
    { 0x35D69E118698A31D, 0x4F7FD3DFBB820BFB }, /* 17 -- 24-16-37 */
    { 0x49613606C466EFD3, 0xFEE2760EF3A900B3 }, /* 18 -- 24-16-37 */
    { 0xBD031D011900A9E5, 0xF0DF0531F434C57D }, /* 19 -- 24-16-37 */
    { 0x235E761B3B378590, 0x442576715266740C }, /* 20 -- 24-16-37 */
    { 0x3710A7AE7945DF77, 0x1E8BAE8F680D2B35 }, /* 21 -- 24-16-37 */
    { 0x75D8E7DBCEDA609C, 0xFD7027FE6D2F6764 }, /* 22 -- 24-16-37 */
    { 0xDE2CBA60CD3332B5, 0x28EFF231AD438124 }, /* 23 -- 24-16-37 */
    { 0x377E64C4E80A06FA, 0x1808760D0A0909A1 }, /* 24 -- 24-16-37 */
    { 0x0CF0A2225DA7FB95, 0xB9A362FAFEDFE9D2 }, /* 25 -- 24-16-37 */
    { 0x2BAB58A3CADFC0A3, 0xF57881AB117349FD }, /* 26 -- 24-16-37 */
    { 0x8D51ECDB9ED82455, 0x849272241425C996 }, /* 27 -- 24-16-37 */
    { 0x521B29D0A57326C1, 0xF1CCB8898CBC07CD }, /* 28 -- 24-16-37 */
    { 0xFBE65017ABEC72DD, 0x61179E44214CAAFA }, /* 29 -- 24-16-37 */
    { 0x6C446B9BC95C267B, 0xD9AA6B1E93FBB6E4 }, /* 30 -- 24-16-37 */
    { 0x64F80248D23655C6, 0x86E3772194563F6D }, /* 31 -- 24-16-37 */
    { 0xFAD843622B252C78, 0xD4E95EEF9EDBDBC6 }, /* 32 -- 24-16-37 */
    { 0x598742BBFDDDE630, 0x05667023C584A68A }, /* 33 -- 24-16-37 */
    { 0x3A9D7DCE072134A6, 0x401AACF87A5E21EE }, /* 34 -- 24-16-37 */
    { 0xF0CC32EAF522F0E0, 0xE114B1E65A950E43 }, /* 35 -- 24-16-37 */
    { 0xEB2BEAA80D3FD8A7, 0x905DFF85834FB8D1 }, /* 36 -- 24-16-37 */
    { 0x61F29536E1BB6B99, 0xC449C069734817CB }, /* 37 -- 24-16-37 */
    { 0x390CD235D35187DA, 0x1E5BC0FE7032F3DF }, /* 38 -- 24-16-37 */
    { 0x744E5F1168BA3345, 0x3F399E6F1EA22DBC }, /* 39 -- 24-16-37 */
    { 0x8CC9AA88A153F5F8, 0xD47A02636F041CCA }, /* 40 -- 24-16-37 */
    { 0x08D037056C80B9E0, 0xF83C06B106D3B7AB }, /* 41 -- 24-16-37 */
    { 0x4CE3C123D196BF7A, 0x14223EEDAE116A83 }, /* 42 -- 24-16-37 */
    { 0xB1B206870DA4E89A, 0x24BFD164204335AE }, /* 43 -- 24-16-37 */
    { 0x207BB2453717CF67, 0x4A5953C8F4BC2A51 }, /* 44 -- 24-16-37 */
    { 0xA14E342BB11FF7E6, 0xF6B3F196DC551CCF }, /* 45 -- 24-16-37 */
    { 0x5422BCA5015DD3B7, 0x5B6233B76FA214D7 }, /* 46 -- 24-16-37 */
    { 0xEDE7341C00C65B85, 0xF20D7136458BD924 }, /* 47 -- 24-16-37 */
    { 0xD769CFC9028DEB78, 0x9B19BA6B3752065A }, /* 48 -- 24-16-37 */
    { 0xC7B0E531ABE7E4BD, 0x4F27796502238C48 }, /* 49 -- 24-16-37 */
    { 0x1C6D3BA4BB94182A, 0xB7B17DCD25003305 }, /* 50 -- 24-16-37 */
    { 0x3AE9471D0E2D0BCF, 0xAAAE579366147D07 }, /* 51 -- 24-16-37 */
    { 0x8F9CD3794CA46FBF, 0x0D56BB288C661CCF }, /* 52 -- 24-16-37 */
    { 0xDB2AD4E9C15A9D4E, 0x0402342EEDFF424C }, /* 53 -- 24-16-37 */
    { 0x79E061AF5BE21395, 0x4E71559E6D0E7F00 }, /* 54 -- 24-16-37 */
    { 0x96E7D88C0794E785, 0x8367AF1C9D6C1406 }, /* 55 -- 24-16-37 */
    { 0xCCDDA809DB64B3E7, 0x0DBFCD2453D1D33F }, /* 56 -- 24-16-37 */
    { 0x6C64681C21CD0286, 0x3309E57F180D4FF6 }, /* 57 -- 24-16-37 */
    { 0xACB8D4C6BA67113E, 0xB439F330AB3B9715 }, /* 58 -- 24-16-37 */
    { 0xBAD04CA5D96E2CD3, 0xC58F079D0205BCF3 }, /* 59 -- 24-16-37 */
    { 0xEBFBC2723A906760, 0x09417D8C80A37AA7 }, /* 60 -- 24-16-37 */
    { 0x38AC01316167183D, 0x52F51AC639E09712 }, /* 61 -- 24-16-37 */
    { 0x7A134006D4EFA484, 0xF37EAD6EA53B96BA }, /* 62 -- 24-16-37 */
    { 0x351561E58F8572D4, 0xDC1C01799CB8D734 }, /* 63 -- 24-16-37 */
    { 0xDF900294D8F554A5, 0x170865DF4B3201FC }, /* 64 -- 24-16-37 */
    { 0x2992EAD4972EAED2, 0xB2A7B279A8CB1F50 }, /* 65 -- 24-16-37 */
    { 0xC026A7D9E04A7700, 0xE7859C665BE57882 }, /* 66 -- 24-16-37 */
    { 0xB4CB6197DEA2B1FE, 0x4B4A7AA8C389701C }, /* 67 -- 24-16-37 */
    { 0x0DCFC5B909E7DF4D, 0xADB7753D55646EEF }, /* 68 -- 24-16-37 */
    { 0x468431669864F789, 0xC80926301806A352 }, /* 69 -- 24-16-37 */
    { 0x22B6C1736285FCC8, 0xC05DA051EC96AF1D }, /* 70 -- 24-16-37 */
    { 0x74C1DAAC8729D8BB, 0xF88F6BAC8FD30448 }, /* 71 -- 24-16-37 */
    { 0x847757C126B23E45, 0x752B98D002C408F7 }, /* 72 -- 24-16-37 */
    { 0x0F9EAA62D0C9E2A3, 0x1AA7BC96DBACE110 }, /* 73 -- 24-16-37 */
    { 0x7475D71B98314377, 0xC469B29353A4984B }, /* 74 -- 24-16-37 */
    { 0xBBB7D266D61C85EA, 0x4B6DD41BCE3BB499 }, /* 75 -- 24-16-37 */
    { 0xC419B3742570E16F, 0xE023777E70B3A2F8 }, /* 76 -- 24-16-37 */
    { 0x2A71DB3A3CE8B968, 0x131E94FB35203D80 }, /* 77 -- 24-16-37 */
    { 0x2897BB8961B4DCE9, 0x9240C95B1E7FA08B }, /* 78 -- 24-16-37 */
    { 0xF0FC3553D7881D5F, 0xB879FCA0915F893F }, /* 79 -- 24-16-37 */
    { 0xE754DB3FBC7536BC, 0x2ADCA86FBEFE1366 }, /* 80 -- 24-16-37 */
    { 0x0A9E201ADFE7BAA9, 0x0A40A688D77855BA }, /* 81 -- 24-16-37 */
    { 0x1D0D601E49C35837, 0x17771C905E0775A8 }, /* 82 -- 24-16-37 */
    { 0x9B031395AEC7B584, 0x2CF775E419A607E0 }, /* 83 -- 24-16-37 */
    { 0x79EAD2EEDDF66699, 0x93A7CF27DEC9B306 }, /* 84 -- 24-16-37 */
    { 0xE1B9805C107679FC, 0x93615189FE85B7D5 }, /* 85 -- 24-16-37 */
    { 0x2C3925DCD790E3D6, 0x466421124B50FBFB }, /* 86 -- 24-16-37 */
    { 0xDCA9B0FA4E95600E, 0x1CDA7BD04E3BB94B }, /* 87 -- 24-16-37 */
    { 0xEFC7905E1CBB5FFB, 0x5EC431D73BBFE49F }, /* 88 -- 24-16-37 */
    { 0x854414811D534483, 0x31A1F85FD532F302 }, /* 89 -- 24-16-37 */
    { 0xADB9BA2958F30B6E, 0xED9B991C09177E2F }, /* 90 -- 24-16-37 */
    { 0x76F8FDF26B0D1CBB, 0x38D9E87DFFDFCA70 }, /* 91 -- 24-16-37 */
    { 0x51F21CDDCEBDB8C7, 0xD8E9E7254052AF4D }, /* 92 -- 24-16-37 */
    { 0xA03F796EFB295305, 0x62769780D13FBC08 }, /* 93 -- 24-16-37 */
    { 0x4F2083F6B19E628A, 0x66E5456C2EAEDBFF }, /* 94 -- 24-16-37 */
    { 0x8B2BE9CD79734BED, 0xACE8D6CE8E3FBA17 }, /* 95 -- 24-16-37 */
    { 0xD2A98B26625EEE7B, 0xDDDF9B1090AA7AC1 }, /* 96 -- 24-16-37 */
    { 0x4FFF128094EDD94C, 0x00D67DC46AD28695 }, /* 97 -- 24-16-37 */
    { 0x726438E9A1D3C6EA, 0xF9540570703E7CF3 }, /* 98 -- 24-16-37 */
    { 0x92CC6A0937C9D34E, 0x066A9599766619B5 }, /* 99 -- 24-16-37 */
    { 0xC5730DE058E1047F, 0xA4E540C7AC49AA1B }, /* 100 -- 24-16-37 */
    { 0xE408BBECDA066551, 0xC2EDFC1AB51C00AD }, /* 101 -- 24-16-37 */
    { 0xC5477EA8821CE588, 0xF11753A4339E78C3 }, /* 102 -- 24-16-37 */
    { 0x3C6058E633063180, 0xBB42E906EFB12540 }, /* 103 -- 24-16-37 */
    { 0xBEC40E0518086E21, 0x4E86F36C495EEEDB }, /* 104 -- 24-16-37 */
    { 0x465276434FD98954, 0xE8345A7C487FEFD6 }, /* 105 -- 24-16-37 */
    { 0x3ADAEA5CDFE12E3B, 0x688B762874221434 }, /* 106 -- 24-16-37 */
    { 0xC9DFFA95904E99B1, 0x833801923A05F253 }, /* 107 -- 24-16-37 */
    { 0xA10C3FB0B18DF787, 0x58A00D23A8086646 }, /* 108 -- 24-16-37 */
    { 0xA4E41F760281C3D0, 0xEC69708D487DBFC4 }, /* 109 -- 24-16-37 */
    { 0xB8880FFF0E41261C, 0x47176F17DE7FF0E9 }, /* 110 -- 24-16-37 */
    { 0x58EE3B30F542767E, 0x4F40C533643920EA }, /* 111 -- 24-16-37 */
    { 0x15F2D25B60C5ACD7, 0x83FD48D6B9620584 }, /* 112 -- 24-16-37 */
    { 0xE448C83950A687EA, 0x0CE303C7D3AABBC8 }, /* 113 -- 24-16-37 */
    { 0xA6FF7863C363CFD4, 0x1746715DF0DD8FE3 }, /* 114 -- 24-16-37 */
    { 0x7E9D8517B195D9C9, 0xC00185964CAEF8BB }, /* 115 -- 24-16-37 */
    { 0x40DDB4DAF3FBDDA8, 0xB6BDE02BD004B144 }, /* 116 -- 24-16-37 */
    { 0x7A794B820672A49B, 0xBA43C63EC5A9F187 }, /* 117 -- 24-16-37 */
    { 0xC1BE31E7536236FB, 0x2467071B1D261621 }, /* 118 -- 24-16-37 */
    { 0xF0EEC34DAEA486FB, 0x5A6FC0435F011DAA }, /* 119 -- 24-16-37 */
    { 0xF42C01A2A3815DB4, 0xA5AF34331C044D81 }, /* 120 -- 24-16-37 */
    { 0xDF7964C343B312DE, 0xDB43B553CD16EA44 }, /* 121 -- 24-16-37 */
    { 0x8454182464C29903, 0x432C2BBCD03E65F6 }, /* 122 -- 24-16-37 */
    { 0x7B6C0ECC6CB5ADBB, 0xCDF56412D1E7BA6E }, /* 123 -- 24-16-37 */
    { 0x380B97764C9F7748, 0xAC13C8B2FF838036 }, /* 124 -- 24-16-37 */
    { 0x1868A9F5A4FD4D64, 0x71D208CC2E5C56E9 }, /* 125 -- 24-16-37 */
    { 0xE89F5FE075D74A79, 0xD1D08A01B73DE005 }, /* 126 -- 24-16-37 */
    { 0x25AA87F3C2704C69, 0xA9495C12936AD0FD }, /* 127 -- 24-16-37 */
};

Vinzent Steinberg

unread,
Oct 8, 2020, 6:44:37 PM10/8/20
to pr...@googlegroups.com
Here are some examples for calculating the jump constants:


Vinzent

--
You received this message because you are subscribed to the Google Groups "prng" group.
To unsubscribe from this group and stop receiving emails from it, send an email to prng+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/prng/129bb962-bb34-437c-8048-e9bcae31492an%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages