Sebastiano Vigna kindly emailed me all the xoroshiro32 characteristic polynomials, essential info for creating jump functions. The weight is the number of terms in the polynomial and in theory close to 16 is preferable. Our best triplet [14,2,7] has weight of 11 and second best [15,3,6] has weight of 13.
I hadn't looked closely at all the full-period triplets before. For every [a,b,c] there is a corresponding [c,b,a] that shares the same characteristic polynomial. Knowing this in advance means brute force searches can be reduced by half.
Hey Tony, thanks for getting that. It perfectly matches our 84 brute forced findings. I only just really looked at it now.
And the recommendation of targeting only the ones of closely matching "degree" with word size will be valuable with what's coming up ... I've spoken with Sebastiano again and, same as you, I just had to ask and he immediately popped me a complete list of full-period candidates for a Xoroshiro64 iterator! Amazing stuff. It isn't nicely sorted in mirror pairs like your one was though.
Excellent news! Thanks for doing that, Evan. I could sort the list into mirror pairs, if you wish.
Tony,
In what I presented to Chip, I chose to revert back to just the earlier iterator only type function so as to limit the logic/flops burden in the instruction of the larger number of bits involved. Also, it keeps the execution to a single clock cycle, which I suspect is not the case with your approach.
Tony,
In what I presented to Chip, I chose to revert back to just the earlier iterator only type function so as to limit the logic/flops burden in the instruction of the larger number of bits involved. Also, it keeps the execution to a single clock cycle, which I suspect is not the case with your approach.
If there are no timing issues with doing a couple of XORs before a 32-bit addition then my XORO64 idea will work.
EDIT:
Two parallel xoroshiro32s would be replaced by one xoroshiro64. The inputs to one of the two parallel 16-bit additions have a two xoroshiro delay in XORO32.
What we have now is ideal, I think, and it's easy-to-use as can be. 32 bits is plenty for most uses, I imagine.
And if a *real* random number is needed, you can always just do a GETRND, without any contingencies.
XORO64 could produce 32-bit PRNs in three instructions. There is a new, simple and optional post-processing that should improve its output. I cannot say any more at the moment. We are getting tremendous help from Sebastiano Vigna, who has been testing the following xoroshiro[32]64 triples:
All xoroshiro generators (without additional backend reworking) at some point have some Hamming dependency kicking in. That is, if you look at the number of ones and zeros in a sequence of, say, 10 consecutive outputs, the resulting 10-tuple doesn't have exactly the distribution it should be, as linear generator tend to create correlation between the number of 1s of consecutive outputs.
In xoroshiro128 this happens after several TB of data (at least 32TB), so it's not a real concern. But in smaller-sized generator it will happen before (e.g., "DC6" test from PractRand).
In this case, testing is fundamental because theory cannot really say much except what is full period and what not.
That email address was just a throw away and it's actually stopped by the provided now, I seriously dislike the "social media" tendrils. Not to mention the horrid comment entry interface that Google Groups has. I'll be a very sad puppy if Parallax ever tries to use such rubbish for it's forums.
It has definitely been helpful reading both Scro's and Seba's comments. It's helped to know what to look for when 100% testing isn't an option ... Here's a summary of what I've got so far:
Note: The full width 32-bit tests top out at 32 GB. All failed with a massive brick wall BRank. I believe this is due to the summed bit1 being shifted into the more sensitive bit0 position for PractRand.
EDIT:
The second column of scores, [31:1], what I've also called Word1 before, shows more substantial results. These all failed on the DC6-9x1Bytes-1 test in PractRand.
PS: The byte sized sampling variants (except for LSByte) feel like they're going to go a lot further. I tested a pair of low quality candidates out to 4 TB (took more than a day) and it wasn't giving up there.
LSByte, [7:0], always dies at 8 GB (exactly quarter of full 32-bit sampling). These have the same massive BRank fails as the full width variant.
EDIT2:
When placing the parity at bit0 the BRank test fails the [31:0] variant at 512 GB instead of 32G. There is a mix of DC6 failures at 256 GB with these. The group of good scores is diminished and not as obvious.
I'm running the parity at bit0 sweep at the moment.
Just remember, Tony, shifting a low quality bit further away from bit0 is not improving quality. It's just tricking Practrand into giving higher scores.
When placing the parity at bit0 the BRank test fails the [31:0] variant at 512 GB instead of 32G. There is a mix of DC6 failures at 256 GB with these. The group of good scores is diminished and not as obvious.
I'm running the parity at bit0 sweep at the moment.
Could you post these Xoroshiro64+p parity at bit0 scores some time?
I overwrote one of the good output files before I'd done the score table. I can post it minus that score ... EDIT: Correction, I did have that score noted already.
Here's the full list, I've only done the Word0 variant:
Yeah, It's probably not as bad as it looks because I think the scoring processed value gets scaled down more for larger datasets but those were bad enough to all fail the DC6 at the 512 MB mark as well as the BRank fail.
EDIT: The reason I included them is the 35.6 is the lowest. Just another datapoint to consider.
The current xoroshiro128+ implementation is as small as can be.
Every cog gets a uniquely-picked/ordered/inverted set of 32 bits from the 63-bit source. Every smart pin gets 8 such bits. Smart pins need these for DAC dithering and noise generation. Cogs need them for the GETRND instruction. I think cogs and pins will all be happy with this arrangement. These patterns really only need to serve as apparently-uncoordinated white noise sources.
On start-up, the PRNG will be 1/4 seeded maybe 64 times with 4 bits of pure thermal noise, along with another 27 bits of process/voltage/temperature-dependent bits.
A few questions:
1. Has the parity improvement been applied to xoroshiro128+ ? That would make a 64-bit source and could mean each bit is used the same number of times for the different cogs and smart pins.
2. Is there enough time to do the 64-bit addition in a single clock?
3. Have the different cog and smart pin scramblings been made public? (I don't want to hold up Chip with this one.)
A few bits get used 9 times, while the rest get used 8 times in those longs. This is because, as you know, we only have 63 bits in x[62:0]. No long uses the same bit twice (cog GETRND sources), nor does any byte (smart pin noise sources). I think the distribution is good enough that adding that parity fix wouldn't make any meaningful difference.
Here is the Spin program for the Prop1 that a I wrote to randomly come up with these patterns:
''*********************************************
''* Pick 16 random 32-tap sets from 63 bits *
''*********************************************
CON
_clkmode = xtal1 + pll16x
_xinfreq = 5_000_000
OBJ
fds : "FullDuplexSerial"
rr : "RealRandom"
VAR
byte poolsize
byte pool[63]
byte uses[63]
byte taps[16*32]
PUB start | i, j, k
'start serial
fds.start(31,30,0,112500)
'start RealRandom
rr.start
'init pool
poolsize := 63
repeat i from 0 to poolsize - 1
pool[i] := i
'pick random tap sets
fds.str(string(13,13,"Picking taps...",13))
repeat j from 0 to 15
'scramble current pool
fds.str(string(13,"Pool "))
fds.hex(j,1)
scramble_pool
optimize_pool
show_pool
'fill a set of taps, track uses
repeat i from 0 to 31
taps[j*32+i] := pool[i]
uses[pool[i]]++
'output tap sets
fds.str(string(13,13,"16 tap sets in Verilog:",13,13))
repeat j from 0 to 15
fds.tx("{")
repeat i from 0 to 31
if rr.random & 1
fds.tx("!")
else
fds.tx(" ")
fds.str(string("x["))
k := taps[j*32+i]
if k < 10
fds.tx("0")
fds.dec(k)
fds.tx("]")
if i <> 31
fds.tx(",")
else
fds.str(string("},",13))
PRI scramble_pool | i, j
repeat 100
repeat i from 0 to poolsize - 1
if rr.random & 3 'mainly rotate
j := pool[i]
if i == poolsize - 1
pool[i] := pool[0]
pool[0] := j
else
pool[i] := pool[i+1]
pool[i+1] := j
PRI optimize_pool | i, j, k
repeat 10
repeat i from 0 to 31
'look for a used pool member in 0..31
if uses[pool[i]] > 0
'see if it can be swapped out with a less-used member in 32+
repeat j from 32 to poolsize - 1
if uses[pool[j]] < uses[pool[i]]
k := pool[i]
pool[i] := pool[j]
pool[j] := k
quit
PRI show_pool | i
'show pool as a bunch of characters with usage underneath, space at 32
fds.tx(13)
repeat i from 0 to poolsize - 1
fds.tx($40 + pool[i])
if i == 31
fds.tx(" ")
fds.tx(13)
repeat i from 0 to poolsize - 1
fds.hex(uses[pool[i]],1)
if i == 31
fds.tx(" ")
fds.tx(13)
2. Is there enough time to do the 64-bit addition in a single clock?
If the answer is yes, I'm wondering whether two 16-bit additions could be done in one clock, with second using result of the first, perhaps with bespoke carry logic.
Comments
Excellent news! Thanks for doing that, Evan. I could sort the list into mirror pairs, if you wish.
No and no, but we do need a separate subtract to get s1 on its own.
Code when keeping sum[0]:
Code when replacing sum[0] with parity:
Weights of 29-33 might not give best results. Good starting point, though.
It is possible to reduce the above to four or only three instructions.
In what I presented to Chip, I chose to revert back to just the earlier iterator only type function so as to limit the logic/flops burden in the instruction of the larger number of bits involved. Also, it keeps the execution to a single clock cycle, which I suspect is not the case with your approach.
If there are no timing issues with doing a couple of XORs before a 32-bit addition then my XORO64 idea will work.
EDIT:
Two parallel xoroshiro32s would be replaced by one xoroshiro64. The inputs to one of the two parallel 16-bit additions have a two xoroshiro delay in XORO32.
XORO64 could produce 32-bit PRNs in three instructions. There is a new, simple and optional post-processing that should improve its output. I cannot say any more at the moment. We are getting tremendous help from Sebastiano Vigna, who has been testing the following xoroshiro[32]64 triples:
The first one is his current recommendation.
XORO32 could be improved probably with a little bit of re-ordering. This is not guesswork. PractRand tests are needed to be sure.
Evan, I tried to contact you by private message from prng forum. If you didn't receive it, please try the same, thanks.
Fire away, what's the improvement?
Xoroshiro64+p PractRand Score Table Summed bit0 removed Parity prepended at bit31 Candidate Deg [31:0] R= [31:1] [31:2] ============================================== [14 4 25] 25 + 32G 5.8 2T [25 4 14] 25 32G 3.2 1T [26 4 9] 25 32G 10.5 256G [11 2 14] 27 32G 10.4 256G [15 2 26] 27 32G 4.2 512G [26 2 15] 27 32G 6.7 512G [13 3 18] 27 + 32G 1.4 512G [12 3 21] 27 32G 2.3 512G [21 3 12] 27 + 32G -0.6 1T [14 4 27] 27 32G 5.8 2T [27 4 14] 27 + 32G 8.3 2T [18 5 7] 27 + 32G 8.3 256G [17 10 6] 27 32G 24.8 256G [20 7 27] 29 32G 20.9 256G [27 7 20] 29 32G 19.6 256G [13 5 28] 31 32G 21.8 512G [28 5 13] 31 32G 12.6 1T [26 9 13] 31 32G 11.1 512G [10 13 19] 31 + 32G 3.9 256G + Indicative good candidates by Seba. R= Raw value of the DC6-9x1Bytes-1 PractRand test for [31:0] sampling variant (Zero is good).Example:
[Low1/32]BRank(12):3K(1) R=+21249 p~= 9e-6398 FAIL !!!!!!!!
EDIT:
The second column of scores, [31:1], what I've also called Word1 before, shows more substantial results. These all failed on the DC6-9x1Bytes-1 test in PractRand.
PS: The byte sized sampling variants (except for LSByte) feel like they're going to go a lot further. I tested a pair of low quality candidates out to 4 TB (took more than a day) and it wasn't giving up there.
LSByte, [7:0], always dies at 8 GB (exactly quarter of full 32-bit sampling). These have the same massive BRank fails as the full width variant.
EDIT2:
When placing the parity at bit0 the BRank test fails the [31:0] variant at 512 GB instead of 32G. There is a mix of DC6 failures at 256 GB with these. The group of good scores is diminished and not as obvious.
I'm running the parity at bit0 sweep at the moment.
Email just sent.
Could you post these Xoroshiro64+p parity at bit0 scores some time?
Here's the full list, I've only done the Word0 variant:
Xoroshiro64+p PractRand Score Table Summed bit0 removed Summed bit0 removed Parity prepended at bit31 Parity appended at bit0 Candidate Deg [31:0] R= [31:1] [31:0] R= ====================================== ============= [14 4 25] 25 + 32G 5.8 2T 512G 48.4 [25 4 14] 25 32G 3.2 1T 512G 44.3 [26 4 9] 25 32G 10.5 256G 256G [11 2 14] 27 32G 10.4 256G 256G [15 2 26] 27 32G 4.2 512G 256G [26 2 15] 27 32G 6.7 512G 256G [13 3 18] 27 + 32G 1.4 512G 512G 48.1 [12 3 21] 27 32G 2.3 512G 256G [21 3 12] 27 + 32G -0.6 1T 512G 45.5 [14 4 27] 27 32G 5.8 2T 512G 35.6 [27 4 14] 27 + 32G 8.3 2T 512G 39.3 [18 5 7] 27 + 32G 8.3 256G 256G [17 10 6] 27 32G 24.8 256G 32G [20 7 27] 29 32G 20.9 256G 32G [27 7 20] 29 32G 19.6 256G 32G [13 5 28] 31 32G 21.8 512G 128G [28 5 13] 31 32G 12.6 1T 256G [26 9 13] 31 32G 11.1 512G 128G [10 13 19] 31 + 32G 3.9 256G 256G + Indicative good candidates by Seba. R= Raw value of the DC6-9x1Bytes-1 PractRand test for [31:0] sampling variant (Zero is good).[17 10 6]
[20 7 27]
[27 7 20]
[13 5 28]
[26 9 13]
I've attached the xoroshiro[32]64+ characteristic polynomials sorted by weight/degree in CSV format.
Big difference in two sets of R values.
EDIT: The reason I included them is the 35.6 is the lowest. Just another datapoint to consider.
A few questions:
1. Has the parity improvement been applied to xoroshiro128+ ? That would make a 64-bit source and could mean each bit is used the same number of times for the different cogs and smart pins.
2. Is there enough time to do the 64-bit addition in a single clock?
3. Have the different cog and smart pin scramblings been made public? (I don't want to hold up Chip with this one.)
assign rnd = { {!x[00], x[62],!x[02], x[28],!x[09], x[55], x[03],!x[34], x[45], x[37],!x[11], x[07],!x[41],!x[50],!x[52],!x[59],!x[27],!x[40], x[01], x[57], x[17],!x[53],!x[24],!x[22],!x[58], x[25], x[16],!x[29],!x[43], x[32],!x[14], x[30]}, {!x[47], x[49],!x[35],!x[38], x[33],!x[31], x[44], x[13], x[06], x[54],!x[05],!x[10],!x[23],!x[19],!x[51], x[20],!x[39],!x[18],!x[46],!x[42], x[36], x[08], x[04], x[60],!x[48],!x[56],!x[26], x[21],!x[12], x[61],!x[15], x[16]}, {!x[23],!x[21],!x[20],!x[47], x[10], x[48], x[51], x[07],!x[19], x[03],!x[50], x[60],!x[36], x[38],!x[33],!x[06],!x[28], x[27], x[00], x[53], x[24], x[52],!x[14],!x[29],!x[04], x[08], x[42],!x[13],!x[45],!x[56],!x[54], x[61]}, {!x[22], x[15], x[41],!x[05], x[59], x[58],!x[35],!x[26],!x[11],!x[12], x[31],!x[01], x[39],!x[43],!x[62],!x[25],!x[55],!x[32],!x[44],!x[02],!x[46],!x[37], x[09], x[17], x[49],!x[18],!x[34], x[40],!x[57], x[30],!x[56],!x[08]}, {!x[37],!x[42],!x[33], x[35], x[39], x[17],!x[10], x[09], x[23],!x[02],!x[60],!x[36], x[18],!x[00], x[32],!x[21],!x[27], x[34], x[20], x[53], x[48], x[15], x[55],!x[14], x[19],!x[62], x[04],!x[29], x[22],!x[28],!x[06], x[03]}, {!x[45], x[26], x[47],!x[43],!x[50],!x[11], x[57],!x[44], x[31],!x[12],!x[41], x[58],!x[13], x[25], x[07],!x[30], x[05],!x[61],!x[49],!x[59], x[46], x[01], x[52],!x[51],!x[32],!x[16],!x[24],!x[38],!x[54],!x[21], x[37], x[40]}, { x[44],!x[30], x[52], x[62],!x[58], x[45], x[38],!x[55], x[00],!x[12], x[14], x[47],!x[13], x[39], x[53], x[40],!x[18], x[31],!x[03], x[41],!x[48],!x[27], x[09],!x[07],!x[17],!x[15],!x[56], x[20], x[16], x[51],!x[59],!x[11]}, { x[04], x[06], x[22], x[26],!x[50], x[29],!x[34], x[19], x[60], x[05],!x[49], x[57],!x[33], x[10],!x[01], x[46], x[24],!x[08], x[25], x[23], x[35],!x[42], x[54], x[43],!x[36],!x[02],!x[31],!x[28], x[13],!x[15],!x[61],!x[53]}, {!x[27], x[44],!x[33], x[52],!x[34], x[29],!x[20],!x[35], x[01], x[11], x[60],!x[14],!x[45], x[10],!x[36], x[22],!x[21],!x[55], x[62],!x[46],!x[16],!x[26],!x[07],!x[30],!x[17], x[51], x[02],!x[48],!x[42], x[43],!x[08], x[19]}, {!x[38], x[49], x[05], x[28],!x[39], x[23],!x[57],!x[25],!x[18],!x[54],!x[61],!x[24],!x[09],!x[03], x[56], x[04], x[41], x[37], x[40],!x[47],!x[00],!x[06],!x[59],!x[50], x[51],!x[26],!x[22], x[32],!x[58], x[27],!x[12], x[48]}, { x[12],!x[17], x[04],!x[54],!x[18], x[02],!x[35], x[44],!x[40], x[50], x[21], x[37], x[15], x[58],!x[19],!x[42], x[41], x[00],!x[47],!x[56], x[46], x[20], x[34], x[11], x[45], x[32],!x[10],!x[60], x[23],!x[62],!x[61], x[13]}, { x[03], x[53],!x[08], x[33], x[29],!x[01], x[07],!x[28],!x[31],!x[24],!x[57], x[25], x[43],!x[49], x[55],!x[38],!x[06],!x[09], x[05],!x[59],!x[30], x[39], x[16],!x[52], x[14], x[21],!x[20],!x[36], x[13],!x[04],!x[37],!x[34]}, {!x[14],!x[36],!x[35],!x[05], x[45],!x[06],!x[54],!x[41], x[23],!x[15],!x[26],!x[49],!x[39], x[30], x[29],!x[38], x[22],!x[01], x[55],!x[43],!x[46], x[52],!x[53], x[40],!x[16], x[27],!x[00],!x[57],!x[18], x[62], x[28],!x[58]}, { x[07], x[10], x[32], x[50], x[03],!x[12], x[59], x[09],!x[19], x[56],!x[44], x[25], x[47],!x[08], x[31],!x[51], x[17], x[42],!x[61],!x[02],!x[33], x[24], x[30], x[04],!x[43], x[48],!x[49],!x[11],!x[22],!x[29],!x[60],!x[38]}, { x[42], x[37], x[10], x[08], x[61], x[21],!x[00], x[20], x[51], x[57],!x[33],!x[01],!x[03],!x[26],!x[32],!x[05],!x[13], x[19],!x[48],!x[31],!x[02],!x[60],!x[07],!x[36],!x[62], x[27],!x[34],!x[14], x[50],!x[16],!x[17], x[11]}, {!x[56],!x[23],!x[28], x[15], x[45], x[09],!x[24],!x[46],!x[53],!x[25],!x[52],!x[39],!x[40], x[44],!x[55], x[54], x[59],!x[21],!x[06], x[08],!x[18],!x[01],!x[11],!x[61], x[47],!x[41], x[12], x[49],!x[20],!x[29], x[35],!x[58]} };A few bits get used 9 times, while the rest get used 8 times in those longs. This is because, as you know, we only have 63 bits in x[62:0]. No long uses the same bit twice (cog GETRND sources), nor does any byte (smart pin noise sources). I think the distribution is good enough that adding that parity fix wouldn't make any meaningful difference.
Here is the Spin program for the Prop1 that a I wrote to randomly come up with these patterns:
''********************************************* ''* Pick 16 random 32-tap sets from 63 bits * ''********************************************* CON _clkmode = xtal1 + pll16x _xinfreq = 5_000_000 OBJ fds : "FullDuplexSerial" rr : "RealRandom" VAR byte poolsize byte pool[63] byte uses[63] byte taps[16*32] PUB start | i, j, k 'start serial fds.start(31,30,0,112500) 'start RealRandom rr.start 'init pool poolsize := 63 repeat i from 0 to poolsize - 1 pool[i] := i 'pick random tap sets fds.str(string(13,13,"Picking taps...",13)) repeat j from 0 to 15 'scramble current pool fds.str(string(13,"Pool ")) fds.hex(j,1) scramble_pool optimize_pool show_pool 'fill a set of taps, track uses repeat i from 0 to 31 taps[j*32+i] := pool[i] uses[pool[i]]++ 'output tap sets fds.str(string(13,13,"16 tap sets in Verilog:",13,13)) repeat j from 0 to 15 fds.tx("{") repeat i from 0 to 31 if rr.random & 1 fds.tx("!") else fds.tx(" ") fds.str(string("x[")) k := taps[j*32+i] if k < 10 fds.tx("0") fds.dec(k) fds.tx("]") if i <> 31 fds.tx(",") else fds.str(string("},",13)) PRI scramble_pool | i, j repeat 100 repeat i from 0 to poolsize - 1 if rr.random & 3 'mainly rotate j := pool[i] if i == poolsize - 1 pool[i] := pool[0] pool[0] := j else pool[i] := pool[i+1] pool[i+1] := j PRI optimize_pool | i, j, k repeat 10 repeat i from 0 to 31 'look for a used pool member in 0..31 if uses[pool[i]] > 0 'see if it can be swapped out with a less-used member in 32+ repeat j from 32 to poolsize - 1 if uses[pool[j]] < uses[pool[i]] k := pool[i] pool[i] := pool[j] pool[j] := k quit PRI show_pool | i 'show pool as a bunch of characters with usage underneath, space at 32 fds.tx(13) repeat i from 0 to poolsize - 1 fds.tx($40 + pool[i]) if i == 31 fds.tx(" ") fds.tx(13) repeat i from 0 to poolsize - 1 fds.hex(uses[pool[i]],1) if i == 31 fds.tx(" ") fds.tx(13)If the answer is yes, I'm wondering whether two 16-bit additions could be done in one clock, with second using result of the first, perhaps with bespoke carry logic.