Welcome to the Parallax Discussion Forums, sign-up to participate.

# Random/LFSR on P2

• Posts: 13,658
cgracey wrote: »
David Betz wrote: »
I assume the new FPGA images with this new random number generator will have the same instruction set and encoding as the current v16. Is that correct?

Yes. This is a very subtle change that almost nobody would recognize, in practice.
Thanks for confirming.

• Posts: 12,109
Of the 63 PRNG bits, I figure that all 63 bits will get used 8 times and 8 of those 63 bits will get used 1 more time. This will keep the fan-out lowest. How to parse this, though?
• Posts: 8,576
cgracey wrote: »
Random pickoff matters, relatively, between sets of 32 bits.

It's kind of a two-dimensional problem. Some divide-and-conquer is needed.
How about dropping the constants and just use differing xor groupings of ss. Becomes 16 variant hashs of the full 63 bits down to 32 bits I guess.
"Those who think we are powerless to do anything about the greenhouse effect forget about the 'White House effect,'" - George H.W. Bush, 1988.
• Posts: 8,576
cgracey wrote: »
... This will keep the fan-out lowest. How to parse this, though?
Is there a big advantage in having the generator being 64-bit in the first place?
"Those who think we are powerless to do anything about the greenhouse effect forget about the 'White House effect,'" - George H.W. Bush, 1988.
• Posts: 8,576
edited 2017-03-04 - 01:49:55
evanh wrote: »
How about dropping the constants and just use differing xor groupings of ss. Becomes 16 variant hashs of the full 63 bits down to 32 bits I guess.
Here's an unrandomised example:
```assign rnd = {
{x[31:00]^x[62:31]},
{x[39:08]^{x[62:39],x[07:00]}},
{}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}
};
```
"Those who think we are powerless to do anything about the greenhouse effect forget about the 'White House effect,'" - George H.W. Bush, 1988.
• Posts: 975
Complete Dieharder results from the original PRNG using bit reordering (I will start a run without bit reordering now)
```#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
rng_name    |rands/second|   Seed   |
stdin_input_raw|  1.82e+06  |1385337568|
#=============================================================================#
test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
diehard_birthdays|   0|       100|     100|0.00000000|  FAILED
diehard_operm5|   0|   1000000|     100|0.00000000|  FAILED
diehard_rank_32x32|   0|     40000|     100|0.00000000|  FAILED
diehard_rank_6x8|   0|    100000|     100|0.00000000|  FAILED
diehard_bitstream|   0|   2097152|     100|0.00000000|  FAILED
diehard_opso|   0|   2097152|     100|0.00000000|  FAILED
diehard_oqso|   0|   2097152|     100|0.00000000|  FAILED
diehard_dna|   0|   2097152|     100|0.00000000|  FAILED
diehard_count_1s_str|   0|    256000|     100|0.00000000|  FAILED
diehard_count_1s_byt|   0|    256000|     100|0.00000000|  FAILED
diehard_parking_lot|   0|     12000|     100|0.00000000|  FAILED
diehard_2dsphere|   2|      8000|     100|0.00000000|  FAILED
diehard_3dsphere|   3|      4000|     100|0.00000000|  FAILED
diehard_squeeze|   0|    100000|     100|0.00000000|  FAILED
diehard_sums|   0|       100|     100|0.31392291|  PASSED
diehard_runs|   0|    100000|     100|0.01074318|  PASSED
diehard_runs|   0|    100000|     100|0.00803469|  PASSED
diehard_craps|   0|    200000|     100|0.00000000|  FAILED
diehard_craps|   0|    200000|     100|0.00000000|  FAILED
marsaglia_tsang_gcd|   0|  10000000|     100|0.00000000|  FAILED
marsaglia_tsang_gcd|   0|  10000000|     100|0.00000000|  FAILED
sts_monobit|   1|    100000|     100|0.00000008|  FAILED
sts_runs|   2|    100000|     100|0.81212684|  PASSED
sts_serial|   1|    100000|     100|0.00000000|  FAILED
sts_serial|   2|    100000|     100|0.00000000|  FAILED
sts_serial|   3|    100000|     100|0.00000000|  FAILED
sts_serial|   3|    100000|     100|0.26169039|  PASSED
sts_serial|   4|    100000|     100|0.00000000|  FAILED
sts_serial|   4|    100000|     100|0.79338330|  PASSED
sts_serial|   5|    100000|     100|0.00000000|  FAILED
sts_serial|   5|    100000|     100|0.33393564|  PASSED
sts_serial|   6|    100000|     100|0.00000000|  FAILED
sts_serial|   6|    100000|     100|0.00000000|  FAILED
sts_serial|   7|    100000|     100|0.00000000|  FAILED
sts_serial|   7|    100000|     100|0.00000000|  FAILED
sts_serial|   8|    100000|     100|0.00000000|  FAILED
sts_serial|   8|    100000|     100|0.00000000|  FAILED
sts_serial|   9|    100000|     100|0.00000000|  FAILED
sts_serial|   9|    100000|     100|0.00000000|  FAILED
sts_serial|  10|    100000|     100|0.00000000|  FAILED
sts_serial|  10|    100000|     100|0.66663122|  PASSED
sts_serial|  11|    100000|     100|0.00000000|  FAILED
sts_serial|  11|    100000|     100|0.00000000|  FAILED
sts_serial|  12|    100000|     100|0.00000000|  FAILED
sts_serial|  12|    100000|     100|0.01778776|  PASSED
sts_serial|  13|    100000|     100|0.00000000|  FAILED
sts_serial|  13|    100000|     100|0.00000000|  FAILED
sts_serial|  14|    100000|     100|0.00000000|  FAILED
sts_serial|  14|    100000|     100|0.00000000|  FAILED
sts_serial|  15|    100000|     100|0.00000000|  FAILED
sts_serial|  15|    100000|     100|0.00000000|  FAILED
sts_serial|  16|    100000|     100|0.00000000|  FAILED
sts_serial|  16|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   1|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   2|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   3|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   4|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   5|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   6|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   7|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   8|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   9|    100000|     100|0.00000000|  FAILED
rgb_bitdist|  10|    100000|     100|0.00000000|  FAILED
rgb_bitdist|  11|    100000|     100|0.00000000|  FAILED
rgb_bitdist|  12|    100000|     100|0.00000000|  FAILED
rgb_minimum_distance|   2|     10000|    1000|0.00000000|  FAILED
rgb_minimum_distance|   3|     10000|    1000|0.00000000|  FAILED
rgb_minimum_distance|   4|     10000|    1000|0.00000000|  FAILED
rgb_minimum_distance|   5|     10000|    1000|0.00000000|  FAILED
rgb_permutations|   2|    100000|     100|0.99989978|   WEAK
rgb_permutations|   3|    100000|     100|0.00000000|  FAILED
rgb_permutations|   4|    100000|     100|0.00000000|  FAILED
rgb_permutations|   5|    100000|     100|0.00000000|  FAILED
rgb_lagged_sum|   0|   1000000|     100|0.61656083|  PASSED
rgb_lagged_sum|   1|   1000000|     100|0.83139925|  PASSED
rgb_lagged_sum|   2|   1000000|     100|0.14442315|  PASSED
rgb_lagged_sum|   3|   1000000|     100|0.64748367|  PASSED
rgb_lagged_sum|   4|   1000000|     100|0.97505881|  PASSED
rgb_lagged_sum|   5|   1000000|     100|0.65316692|  PASSED
rgb_lagged_sum|   6|   1000000|     100|0.37269121|  PASSED
rgb_lagged_sum|   7|   1000000|     100|0.66544910|  PASSED
rgb_lagged_sum|   8|   1000000|     100|0.62631348|  PASSED
rgb_lagged_sum|   9|   1000000|     100|0.31158884|  PASSED
rgb_lagged_sum|  10|   1000000|     100|0.09620060|  PASSED
rgb_lagged_sum|  11|   1000000|     100|0.50465463|  PASSED
rgb_lagged_sum|  12|   1000000|     100|0.94123827|  PASSED
rgb_lagged_sum|  13|   1000000|     100|0.87572616|  PASSED
rgb_lagged_sum|  14|   1000000|     100|0.29949509|  PASSED
rgb_lagged_sum|  15|   1000000|     100|0.91225994|  PASSED
rgb_lagged_sum|  16|   1000000|     100|0.85992301|  PASSED
rgb_lagged_sum|  17|   1000000|     100|0.10002499|  PASSED
rgb_lagged_sum|  18|   1000000|     100|0.26246601|  PASSED
rgb_lagged_sum|  19|   1000000|     100|0.18881850|  PASSED
rgb_lagged_sum|  20|   1000000|     100|0.56157055|  PASSED
rgb_lagged_sum|  21|   1000000|     100|0.05753914|  PASSED
rgb_lagged_sum|  22|   1000000|     100|0.30578792|  PASSED
rgb_lagged_sum|  23|   1000000|     100|0.24124016|  PASSED
rgb_lagged_sum|  24|   1000000|     100|0.52633383|  PASSED
rgb_lagged_sum|  25|   1000000|     100|0.28961217|  PASSED
rgb_lagged_sum|  26|   1000000|     100|0.13990288|  PASSED
rgb_lagged_sum|  27|   1000000|     100|0.72070403|  PASSED
rgb_lagged_sum|  28|   1000000|     100|0.92355423|  PASSED
rgb_lagged_sum|  29|   1000000|     100|0.70936471|  PASSED
rgb_lagged_sum|  30|   1000000|     100|0.55076650|  PASSED
rgb_lagged_sum|  31|   1000000|     100|0.64104031|  PASSED
rgb_lagged_sum|  32|   1000000|     100|0.04751119|  PASSED
rgb_kstest_test|   0|     10000|    1000|0.00000000|  FAILED
dab_bytedistrib|   0|  51200000|       1|0.00000000|  FAILED
dab_dct| 256|     50000|       1|0.00000000|  FAILED
Preparing to run test 207.  ntuple = 0
dab_filltree|  32|  15000000|       1|0.00000000|  FAILED
dab_filltree|  32|  15000000|       1|0.00000000|  FAILED
Preparing to run test 208.  ntuple = 0
dab_filltree2|   0|   5000000|       1|0.00000000|  FAILED
dab_filltree2|   1|   5000000|       1|0.00000000|  FAILED
Preparing to run test 209.  ntuple = 0
dab_monobit2|  12|  65000000|       1|1.00000000|  FAILED

```
SIDcog - The sound of the Commodore 64 in a single cog: Thread, OBEX
• Posts: 12,109
edited 2017-03-04 - 09:49:18
The XOR'ing idea is good, I think, but it would cause delays, since there'd be some logic to go through before interconnect amps and delays. Coming out of a flop is a lot faster.

I made a program which randomly selects sixteen 32-bit tap sets from the 63-bit PRNG output. It uses RealRandom to shuffle the data and then it optimizes the tap usage to minimize fan-out. It generates this, for example:
```{!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]},
```

I wrote the generator in Spin. I realize in Spin2, we'll need a SWAP(v1,v2) instruction. We'll also need to clean up the string syntax and make it terser.

Here's the Spin program that generates the random tap sets:

• Posts: 975
edited 2017-03-04 - 10:09:58
I tried to solve Chips programming challenge using brute force. Randomize everything and see if each bit gets tapped 8 or 9 times. Of course I did expect it to take a long time, but with a little bit of math and by measuring the factor between getting 3 and 4 bits right I can say it's not feasible. It would take 1,1013671599500632751e50 seconds on my computer!
SIDcog - The sound of the Commodore 64 in a single cog: Thread, OBEX
• Posts: 12,109
Ahle2 wrote: »
Chip, evanh,

I tried to solve Chips programming challenge using brute force. Randomize everything and see if each bit gets tapped 8 or 9 times. Of course I did expect it to take a long time, but with a little bit of math and by measuring the factor between getting 3 and 4 bits right I can say it's not feasible. It would take 1,1013671599500632751e50 seconds on my computer!

I made a program to do it in the post above. I just shuffle the deck, use the first 32, and track how many times each tap has been used. After shuffling the deck, though, I need to swap less-used taps into the lower 32 positions. It turns out that it uses 55 bits 8 times over and the other 8 bits 9 times over, which is optimal.

Thanks for working on this, Ahle2. I didn't know if anybody was going to work on it, so I spent some time figuring it out. It's been really quiet on the forum all day, after maybe 60 posts yesterday.
• Posts: 8,576
edited 2017-03-05 - 00:51:18
Chip,
If there was a desire to even that out to 8 uses for each bit then extending the ss result to 64 bits wouldn't take much. Just make the s0 + s1 adder have 65-bit result.
"Those who think we are powerless to do anything about the greenhouse effect forget about the 'White House effect,'" - George H.W. Bush, 1988.
• Posts: 12,109
evanh wrote: »
Chip,
If there was a desire to even that out to 8 uses for each bit then extending the ss result to 64 bits wouldn't take much. Just make the s0 + s1 adder have 65-bit result.

That would effectively be the carry output, right? I wonder if its behavior would pass all those tests that the other bits did.
• Posts: 22,516
Chip,

What happens with your shuffle algo if the 64-bit random result turns out to have just one "1" bit in it? It could occur.

-Phil
Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
• Posts: 12,109
Chip,

What happens with your shuffle algo if the 64-bit random result turns out to have just one "1" bit in it? It could occur.

-Phil

I don't understand. That doesn't seem like a problem.

Someone said something that made me see things differently: If all those tests were passed in Dieharder, then every bit of output is like it's own TRNG. Therefore, it doesn't matter if you switch their positions around or statically invert some of them.
• Posts: 22,516
I guess what I was thinking is that such an unbalance of ones vs. zeroes would increase the likelihood that two or more of the derivative 32-bit results would be identical -- in my hypothetical case, all zeroes. But maybe that's not a problem?

-Phil
Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
• Posts: 12,109
I guess what I was thinking is that such an unbalance of ones vs. zeroes would increase the likelihood that two or more of the derivative 32-bit results would be identical -- in my hypothetical case, all zeroes. But maybe that's not a problem?

-Phil

extreme imbalances are rare, but part of the idea, I guess.
• Posts: 12,109
Ahle2 wrote: »
Running on average 2^32 iterations to see if it ever returns zero should just take some minutes seconds. Hopefully the PRNG is better than this!

This was pretty funny.
• Posts: 22,516
edited 2017-03-05 - 04:42:51
Chip,

Perhaps I'm mistaken, but I believe what you want is for the 16 32-bit values derived from a single 64-bit value to be statistically independent from each other. Right? I guess what concerns me is that, as the imbalance of ones to zeroes in that 64-bit value increases, the likelihood of statistical independence of the 32-bit values decreases dramatically. Admittedly, this is just a gut feeling. Hopefully, the analysis of some Monte Carlo simulations will prove me wrong, but I would not put a wager on that being the case.

-Phil
Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
• Posts: 8,576
cgracey wrote: »
evanh wrote: »
Chip,
If there was a desire to even that out to 8 uses for each bit then extending the ss result to 64 bits wouldn't take much. Just make the s0 + s1 adder have 65-bit result.

That would effectively be the carry output, right? I wonder if its behavior would pass all those tests that the other bits did.
Include the Carry, yep. Sequence doesn't change since the add exists outside the loop but obviously bit 63 of the result pops into existence, so that would have to be factored into any comparison.
"Those who think we are powerless to do anything about the greenhouse effect forget about the 'White House effect,'" - George H.W. Bush, 1988.
• Posts: 21,233
Yes, that is the problem. How to magically create 16 PRNG running in parallel from a single PRNG in such a way that one cannot tell they are related. The guys doing lots of simulation work on super computers worry about this a lot.

I'm not sure if that is even possible.

The best thing is to have 16 independent PRNG. That boils down to the problem of generating 16 seeds from a single seed in such a way that the PRNGS are all operating in different parts of the state space and will not overlap in state space during any feasible run time.

xoroshiro 128+ includes a method to solve this problem. One can take a single seed and generate up to 2^64 other seeds from it each of which can be used to drive a PRNG with a 2^64 state space that will not overlap with any other.

This is done with the JUMP function:
```/* This is the jump function for the generator. It is equivalent
to 2^64 calls to next(); it can be used to generate 2^64
non-overlapping subsequences for parallel computations. */

void jump(void) {
static const uint64_t JUMP[] = { 0xbeac0467eba5facb, 0xd86b048b86aa9922 };

uint64_t s0 = 0;
uint64_t s1 = 0;
for(int i = 0; i < sizeof JUMP / sizeof *JUMP; i++)
for(int b = 0; b < 64; b++) {
if (JUMP[i] & 1ULL << b) {
s0 ^= s[0];
s1 ^= s[1];
}
next();
}

s[0] = s0;
s[1] = s1;
}
```

My guess is this solution starts to get too big to put into hardware.

I'd be inclined to just arrange that no single PRNG value is ever used more than once. With or without any bit shuffling/inverting. That is to say be sure the PRNG advances by one step for every random number requested by anyone.

• Posts: 975
Results from original P2 PRNG without bit reordering
```#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
rng_name    |rands/second|   Seed   |
stdin_input_raw|  1.26e+07  |2130066915|
#=============================================================================#
test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
diehard_birthdays|   0|       100|     100|0.00000000|  FAILED
diehard_operm5|   0|   1000000|     100|0.00000000|  FAILED
diehard_rank_32x32|   0|     40000|     100|0.00000000|  FAILED
diehard_rank_6x8|   0|    100000|     100|0.00000000|  FAILED
diehard_bitstream|   0|   2097152|     100|0.00000000|  FAILED
diehard_opso|   0|   2097152|     100|0.00000000|  FAILED
diehard_oqso|   0|   2097152|     100|0.00000000|  FAILED
diehard_dna|   0|   2097152|     100|0.00000000|  FAILED
diehard_count_1s_str|   0|    256000|     100|0.00000000|  FAILED
diehard_count_1s_byt|   0|    256000|     100|0.00000000|  FAILED
diehard_parking_lot|   0|     12000|     100|0.00000000|  FAILED
diehard_2dsphere|   2|      8000|     100|0.00000000|  FAILED
diehard_3dsphere|   3|      4000|     100|0.00000000|  FAILED
diehard_squeeze|   0|    100000|     100|0.00000000|  FAILED
diehard_sums|   0|       100|     100|0.49236819|  PASSED
diehard_runs|   0|    100000|     100|0.00000000|  FAILED
diehard_runs|   0|    100000|     100|0.00000000|  FAILED
diehard_craps|   0|    200000|     100|0.00000000|  FAILED
diehard_craps|   0|    200000|     100|0.00000000|  FAILED
marsaglia_tsang_gcd|   0|  10000000|     100|0.00000000|  FAILED
marsaglia_tsang_gcd|   0|  10000000|     100|0.00000000|  FAILED
sts_monobit|   1|    100000|     100|0.00000005|  FAILED
sts_runs|   2|    100000|     100|0.00000000|  FAILED
sts_serial|   1|    100000|     100|0.00000041|  FAILED
sts_serial|   2|    100000|     100|0.00000000|  FAILED
sts_serial|   3|    100000|     100|0.00000000|  FAILED
sts_serial|   3|    100000|     100|0.00000000|  FAILED
sts_serial|   4|    100000|     100|0.00000000|  FAILED
sts_serial|   4|    100000|     100|0.00000000|  FAILED
sts_serial|   5|    100000|     100|0.00000000|  FAILED
sts_serial|   5|    100000|     100|0.00000000|  FAILED
sts_serial|   6|    100000|     100|0.00000000|  FAILED
sts_serial|   6|    100000|     100|0.00000000|  FAILED
sts_serial|   7|    100000|     100|0.00000000|  FAILED
sts_serial|   7|    100000|     100|0.00000000|  FAILED
sts_serial|   8|    100000|     100|0.00000000|  FAILED
sts_serial|   8|    100000|     100|0.00000000|  FAILED
sts_serial|   9|    100000|     100|0.00000000|  FAILED
sts_serial|   9|    100000|     100|0.00000000|  FAILED
sts_serial|  10|    100000|     100|0.00000000|  FAILED
sts_serial|  10|    100000|     100|0.00000000|  FAILED
sts_serial|  11|    100000|     100|0.00000000|  FAILED
sts_serial|  11|    100000|     100|0.00000000|  FAILED
sts_serial|  12|    100000|     100|0.00000000|  FAILED
sts_serial|  12|    100000|     100|0.00000000|  FAILED
sts_serial|  13|    100000|     100|0.00000000|  FAILED
sts_serial|  13|    100000|     100|0.00000000|  FAILED
sts_serial|  14|    100000|     100|0.00000000|  FAILED
sts_serial|  14|    100000|     100|0.00000000|  FAILED
sts_serial|  15|    100000|     100|0.00000000|  FAILED
sts_serial|  15|    100000|     100|0.00000000|  FAILED
sts_serial|  16|    100000|     100|0.00000000|  FAILED
sts_serial|  16|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   1|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   2|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   3|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   4|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   5|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   6|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   7|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   8|    100000|     100|0.00000000|  FAILED
rgb_bitdist|   9|    100000|     100|0.00000000|  FAILED
rgb_bitdist|  10|    100000|     100|0.00000000|  FAILED
rgb_bitdist|  11|    100000|     100|0.00000000|  FAILED
rgb_bitdist|  12|    100000|     100|0.00000000|  FAILED
rgb_minimum_distance|   2|     10000|    1000|0.00000000|  FAILED
rgb_minimum_distance|   3|     10000|    1000|0.00000000|  FAILED
rgb_minimum_distance|   4|     10000|    1000|0.00000000|  FAILED
rgb_minimum_distance|   5|     10000|    1000|0.00000000|  FAILED
rgb_permutations|   2|    100000|     100|0.31163984|  PASSED
rgb_permutations|   3|    100000|     100|0.00000000|  FAILED
rgb_permutations|   4|    100000|     100|0.00000000|  FAILED
rgb_permutations|   5|    100000|     100|0.00000000|  FAILED
rgb_lagged_sum|   0|   1000000|     100|0.98261992|  PASSED
rgb_lagged_sum|   1|   1000000|     100|0.48807245|  PASSED
rgb_lagged_sum|   2|   1000000|     100|0.35271091|  PASSED
rgb_lagged_sum|   3|   1000000|     100|0.77439189|  PASSED
rgb_lagged_sum|   4|   1000000|     100|0.75118990|  PASSED
rgb_lagged_sum|   5|   1000000|     100|0.83707751|  PASSED
rgb_lagged_sum|   6|   1000000|     100|0.24343711|  PASSED
rgb_lagged_sum|   7|   1000000|     100|0.97681044|  PASSED
rgb_lagged_sum|   8|   1000000|     100|0.74407693|  PASSED
rgb_lagged_sum|   9|   1000000|     100|0.85815772|  PASSED
rgb_lagged_sum|  10|   1000000|     100|0.88590719|  PASSED
rgb_lagged_sum|  11|   1000000|     100|0.28589723|  PASSED
rgb_lagged_sum|  12|   1000000|     100|0.41397485|  PASSED
rgb_lagged_sum|  13|   1000000|     100|0.28081672|  PASSED
rgb_lagged_sum|  14|   1000000|     100|0.81096109|  PASSED
rgb_lagged_sum|  15|   1000000|     100|0.20594569|  PASSED
rgb_lagged_sum|  16|   1000000|     100|0.86498183|  PASSED
rgb_lagged_sum|  17|   1000000|     100|0.99570450|   WEAK
rgb_lagged_sum|  18|   1000000|     100|0.85728156|  PASSED
rgb_lagged_sum|  19|   1000000|     100|0.64818851|  PASSED
rgb_lagged_sum|  20|   1000000|     100|0.45480794|  PASSED
rgb_lagged_sum|  21|   1000000|     100|0.53170652|  PASSED
rgb_lagged_sum|  22|   1000000|     100|0.88602349|  PASSED
rgb_lagged_sum|  23|   1000000|     100|0.99206933|  PASSED
rgb_lagged_sum|  24|   1000000|     100|0.55764663|  PASSED
rgb_lagged_sum|  25|   1000000|     100|0.83866851|  PASSED
rgb_lagged_sum|  26|   1000000|     100|0.45077292|  PASSED
rgb_lagged_sum|  27|   1000000|     100|0.79719375|  PASSED
rgb_lagged_sum|  28|   1000000|     100|0.99716738|   WEAK
rgb_lagged_sum|  29|   1000000|     100|0.82790995|  PASSED
rgb_lagged_sum|  30|   1000000|     100|0.85548821|  PASSED
rgb_lagged_sum|  31|   1000000|     100|0.01365643|  PASSED
rgb_lagged_sum|  32|   1000000|     100|0.32007171|  PASSED
rgb_kstest_test|   0|     10000|    1000|0.00000000|  FAILED
dab_bytedistrib|   0|  51200000|       1|0.28255495|  PASSED
dab_dct| 256|     50000|       1|0.00000000|  FAILED
Preparing to run test 207.  ntuple = 0
dab_filltree|  32|  15000000|       1|0.00000000|  FAILED
dab_filltree|  32|  15000000|       1|0.00000000|  FAILED
Preparing to run test 208.  ntuple = 0
dab_filltree2|   0|   5000000|       1|0.00000000|  FAILED
dab_filltree2|   1|   5000000|       1|0.00000000|  FAILED
Preparing to run test 209.  ntuple = 0
dab_monobit2|  12|  65000000|       1|1.00000000|  FAILED
```
SIDcog - The sound of the Commodore 64 in a single cog: Thread, OBEX
• Posts: 8,576
edited 2017-03-05 - 08:45:53
Heater. wrote: »
I'd be inclined to just arrange that no single PRNG value is ever used more than once. With or without any bit shuffling/inverting. That is to say be sure the PRNG advances by one step for every random number requested by anyone.
Not a good idea, imho. The simple way would sacrifice speed and a little determinism. The more complex way sacrifices determinism and a little speed. The expensive way, as you've already noted, takes too much silicon.

Cogs have no need to be secured from each other. Propeller isn't targetting general computing.

"Those who think we are powerless to do anything about the greenhouse effect forget about the 'White House effect,'" - George H.W. Bush, 1988.
• Posts: 21,233
I though the idea was the the PRNG was continuously being clocked in the background. Endlessly stepping through it's sequence no matter if anybody read a random number form it or not. That is to say most of the random numbers get missed.

As such I would suspect that the independence of the random sequence that any COG sees, from any other, is good enough for all practical purposes. With or without bit shuffling.

GOGs will be waiting on I/O and timers etc so multiple COGs won't even be reading the PRNG in the same order all the time. Which randomizes things even more.

The downside of this is perhaps power consumption. Stepping the PRNG when it's output is not used.

• Posts: 21,233
The words "secure" and "cryptographic" have popped up on this thread.

I'm pretty sure the xoroshiro128+ PRNG is not regarded as a Cryptographically Strong RRNG (CSPRNG) and security gurus would frown at using it for cryptographic purposes.

Depends how secure you want to be I guess.
• Posts: 8,576
Yep, all of the above. I imagine it's power cost will be about four 32-bit timers. Adders are linear and not much more than a counter I think. The 16 way shuffled order doesn't cost any extra silicon or power, that's why it's being included.
"Those who think we are powerless to do anything about the greenhouse effect forget about the 'White House effect,'" - George H.W. Bush, 1988.
• Posts: 12,109
edited 2017-03-05 - 09:18:05
The state of the PRNG does advance on every clock, regardless of whether it's being used anywhere.

Each cog receives a unique subset of 32 bits from the PRNG's 63 output bits. Those bits were randomly chosen the other day by the Spin program I made to pick them out, and they are in random order. Some of the bits are always inverted.

Each smart pin gets a unique subset of 8 bits from the PRNG, with some bits always inverted.

All these bit groups and inversions were chosen using RealRandom as a TRNG source.

While all cogs and smart pins receive data from the same PRNG, they each get different versions, with different bits and different inversions. This is probably overkill, but it was done to make every point of usage unique.

Here are the 16 unique longs that go to each cog. And each byte's worth goes to a different smart pin (64 total). The source of this data is the xoroshiro128+ PRNG which outputs x[62:0], which was randomly spread all over and randomly inverted to make these tap sets:
```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]} };
```
• Posts: 8,576
Why was the lsb of ss removed to give 63 bit result?
"Those who think we are powerless to do anything about the greenhouse effect forget about the 'White House effect,'" - George H.W. Bush, 1988.
• Posts: 12,109
edited 2017-03-05 - 09:33:43
evanh wrote: »
Why was the lsb of ss removed to give 63 bit result?

Because it's only an LFSR, according to the xoroshiro128+ documentation. It wouldn't pass the tests.

As you pointed out, though, the carry output of the final adder would seem to be of good quality, but it must not be if they didn't mention it, because it would have been a great way to get a full 64 bits out of the PRNG.
• Posts: 8,576
cgracey wrote: »
evanh wrote: »
Why was the lsb of ss removed to give 63 bit result?
Because it's only an LFSR, according to the xoroshiro128+ documentation. It wouldn't pass the tests.
What? The bottom bit only?

Actually, I might have found the source of it, Heater dug up an example 32-bit conversion that used [32:01] - http://forums.parallax.com/discussion/comment/1402202/#Comment_1402202
"Those who think we are powerless to do anything about the greenhouse effect forget about the 'White House effect,'" - George H.W. Bush, 1988.
• Posts: 21,233
Because there is a comment in the original source code of xoroshiro128+ which says:

"
Beside passing BigCrush, this generator passes the PractRand test suite
up to (and included) 16TB, with the exception of binary rank tests,
which fail due to the lowest bit being an LFSR; all other bits pass all
tests. We suggest to use a sign test to extract a random Boolean value.
"

So basically the LSB taken alone is not as "random" as the other bits. it's a simple Linear Feedback Shift Register PRNG. It probably has a very short sequence compared to the 10^128 sequence length of the rest of the bits.
• Posts: 8,576
Hmm, I guess that means we have no clear answer for the summing carry bit either but I'd imagine it is a function of the lower bits.
"Those who think we are powerless to do anything about the greenhouse effect forget about the 'White House effect,'" - George H.W. Bush, 1988.