Random/LFSR on P2 - Page 66 — Parallax Forums

# Random/LFSR on P2

• Posts: 14,608
-s1 is a sum.
• Posts: 14,608
Oh, oops, it's not a negative, the squiggly is just another xor.
• Posts: 14,608
Huh, so, an integer shifted right by 1 and xor'd with -1 produces the Gray coded value, correct?
• Posts: 309
edited 2019-04-01 02:08
@TonyB There is no third sum (spoken like Picard's line from Star Trek).
The narrow B=1 with inversion, along with other constants (5 and 14), seems to make up once ++ logic is applied.
Larger values of B leave more bits of s1 untouched, which might explain much of the improvement I see.
I also found it superior using the simple output scrambler (x + y) * 5 for both this and the original, which is useful in masking binary matrix rank and related failures.
I'm too close to this, so must take my hands off to let others see if it is useful.
• Posts: 309
edited 2019-04-01 02:59
@evanh Oh, I see the confusion. From C++ docs:
~ NOT Unary complement (bit inversion)
```~s1 ^ (s1 >> Constant_B )
```
Could also be written (and executes faster) as:
```0xffff ^ s1 ^ (s1 >> Constant_B )
```
When B=1, all but one bit changes in the result if s1 were incremented by 1.

Whereas Gray Code would be simply:
```s1 ^ (s1 >> 1)
```
Which would only cause only 1 bit to change if s1 were incremented by 1.

How using an inverted Gray Code in this context improves randomness, I am not entirely certain. However, the escape from zero benefit is somewhat obvious, thus perhaps related.
• Posts: 14,608
Whereas Gray Code would be simply:
```s1 ^ (s1 >> 1)
```
I had no idea it was that few steps! How cool.
• Posts: 14,608
@evanh Oh, I see the confusion. From C++ docs:
~ NOT Unary complement (bit inversion)
I'd just misread the symbol as a minus because of this 4k display and wasn't being careful.
• Posts: 14,608
Kind of pointless having the higher res when all you end up doing is increasing the font size. Sigh.

• Posts: 14,608
I also found it superior using the simple output scrambler (x + y) * 5 for both this and the original, which is useful in masking binary matrix rank and related failures.
I'm too close to this, so must take my hands off to let others see if it is useful.

I'm confident Melisa would dis the * 5 on the scrambler. It keeps Practrand happy but fails in a different way than quality - because it's a non-iterated constant it's too invertible. I think that's the basic idea.
• Posts: 14,608
x + 5 * y might achieve both.
• Posts: 309
edited 2019-04-01 04:50
evanh wrote: »
Kind of pointless having the higher res when all you end up doing is increasing the font size. Sigh.
I could barely tolerate 4K at standard scale on my old Seiki 39" with my poor vision .
I switched to a 49" Sony, which works very well, but my wife keeps taking my mouse away from it (to keep me from ruining my eyes... too late).
So here I sit, RDPing into my main workstations to post here from a 12yo PC with a 27" HD monitor. The tilde character is quite large.
evanh wrote: »
x + 5 * y might achieve both.
I'm not sure if that would work or not. I was only using the * scrambler to help characterize randomness before applying a plusplus scrambler.
Even Seba seemingly cannot predict what will happen once the plusplus scrambler is applied (especially at larger state sizes) with a given set of constants, other than two possible outcomes: Improved randomness or damaged randomness?
I wish the solution to that question would be mathematically provable, as I think the ++ scrambler can be fantastic.
I will note here that in general: D = Width/2+1 (e.g. 9 for 16-bit output), but obviously there are choices for ABC that would prevent that generalized solution from working best, as you have found.
• Posts: 309
edited 2019-04-01 05:11
Here are some tables from my group post:
Escape-from-zero behavior with only 1 state bit set (in average bits set per for 10 consecutive 16-bit outputs):
```Xoroshiro32pp (13,5,10,9) 1.5     5.375    6.96875    7.96875    8.75       8.1875     7.46875    8.6875    8.375     8.5
Xoroshiro32ppg (5,1,14,9) 1.5    10.375    6.5        7.34375    8.59375    8.03125    7.875      8.25      8.0625    7.59375
```
Here are the standard (+) and inverted Gray modified (+g) escape-from-zero values for comparison:
```Xoroshiro32+  (13,5,10)   1       3.1875   5.125      8.28125    7.59375    7.625      8.34375    8.40625   8         7.625
Xoroshiro32+g (5,1,14)    1      13.375    7.84375    8.3125     8          8          8.03125    8.15625   8.09375   8.53125
```
Post back if you do any further testing on this or have any questions.
• Posts: 14,608
I assumed that was the whole scrambler. As in x being s0 and y being s1.

Be aware that existing ++ scrambler is already a longer logic path than the engine is. Adding to it is pushing things to fit in a single clock cycle.
• Posts: 309
edited 2019-04-01 07:16
The output scrambler has not changed, only the engine.
Besides constants, the only change from xoro32++ is that ‘s1 ^ (s1 << B )’ becomes ‘~s1 ^ (s1 >> B )’.
The ‘g’ in ppg refers to that change when B=1, but the name may be altered if other B are found more suitable.
I hate naming conventions, as they never seem to expand the way one intends.
• Posts: 14,608
I mean where does (x + y) * 5 fit in? Initially, it seemed like you were talking about an alternative scrambler. My response about Melisa was pertaining to it replacing the ++ scrambler.
• Posts: 309
Sorry about the confusion, as (x + y) * 5 was only used as part of the vetting process when making changes to the engine. It is not in the source code I posted. Using it seemed to save time, since I didn’t have to consider a D constant until I explored all valid A and C (with B=1, since I was testing inverted Gray codes on a hunch).

The ++ scrambler is like a turbo-charger... you only use it once you are sure the engine is sound.
• Posts: 14,608
Cool. I'll see about getting out the old code and doing some pair distribution runs for you ...
• Posts: 2,077
What are the full-length candidates for this new engine?
• Posts: 14,608
Run of first 20 outputs to verify using the reconfigurable source algorithm (Sources attached):
```0201
bc5d
f539
b323
e4ce
fc84
5cf0
4c72
054b
7b50
1d63
e997
7121
c9ff
48ac
c11a
6f52
ec37
2431
4d25
```
• Posts: 2,077
edited 2019-04-01 11:16
deleted
• Posts: 14,608
I've called the new one Xorograyro32++. With parameters of [5 1 14 9]. Same seed of 1.

• Posts: 14,608
Here's the distribution for Xorograyro32++ [5 1 14 9]. pdist total is spot on. zdist and nzdist totals are a little out.
• Posts: 14,608
I've got some rusty code here. The old full-period search hasn't been used for ages and is missing lots of the later improvements.
• Posts: 2,077
Evan, sorry, I misread the C constant and I do agree with your values.
• Posts: 2,077
edited 2019-04-01 11:24
I think the best name is xoroshironot as that describes the algorithm: xor, rotate, shift, rotate, not. Thus xoroshironot32++ [5,1,14,9].
• Posts: 2,077
evanh wrote: »
Here's the distribution for Xorograyro32++ [5 1 14 9]. pdist total is spot on. zdist and nzdist totals are a little out.

None of them is very good, sadly.
• Posts: 14,608
TonyB_ wrote: »
None of them is very good, sadly.

Worth trying some other candidates of the algorithm? I'm polishing up the full-period search right now ...

• Posts: 2,077
evanh wrote: »
TonyB_ wrote: »
None of them is very good, sadly.

Worth trying some other candidates of the algorithm? I'm polishing up the full-period search right now ...

Could be, only way to find out ...
• Posts: 2,077
xoroshiro32++ pfreq distributions:
```# Pair frequency

# Actual
# a,  b,  c,  d,     pfreq0,     pfreq1,     pfreq2,     pfreq3,     pfreq4,     pfreq5,     pfreq6,     pfreq7,     pfreq8,     pfreq9,    pfreq10,    pfreq11,    pfreq12
# ideal  , , , , 1580030169, 1580030169,  790015084,  263338361,   65834590,   13166918,    2194486,     313498,      39187,       4354,        435,         40,          3
# scro   , , , , 1580017722, 1580044833,  790021507,  263329166,   65837043,   13165427,    2194052,     313378,      39360,       4320,        448,         36,          3
13,  5, 10,  9, 1580109068, 1579940482,  789973580,  263380902,   65840007,   13169609,    2196174,     313409,      39161,       4403,        463,         34,          4
13,  5,  8, 10, 1580149780, 1579894440,  789958573,  263388530,   65849427,   13173791,    2195599,     312821,      39474,       4340,        472,         45,          4
14,  2,  7,  6, 1579336929, 1580735764,  790348643,  263221421,   65684445,   13109945,    2176642,     310656,      38143,       4228,        446,         32,          1
6,  2,  3,  9, 1580730460, 1579315044,  789689377,  263452640,   65972304,   13231825,    2212851,     317581,      40351,       4412,        419,         27,          5
3,  2,  6,  9, 1578177966, 1581892430,  790911930,  263055326,   65442410,   12998176,    2145567,     301689,      37396,       3986,        382,         37,          0
14,  2,  7,  5, 1576661053, 1583423321,  791674049,  262776786,   65121487,   12864448,    2110786,     295138,      35867,       3945,        372,         41,          3

# |Actual-Ideal|^2/Ideal
# a,  b,  c,  d,     pfreq0,     pfreq1,     pfreq2,     pfreq3,     pfreq4,     pfreq5,     pfreq6,     pfreq7,     pfreq8,     pfreq9,    pfreq10,    pfreq11,    pfreq12,      total
# ideal  , , , ,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0
# scro   , , , ,          0,          0,          0,          0,          0,          0,          0,          0,          1,          0,          0,          0,          0,          3
13,  5, 10,  9,          4,          5,          2,          7,          0,          1,          1,          0,          0,          1,          2,          1,          0,         24
13,  5,  8, 10,          9,         12,          4,         10,          3,          4,          1,          1,          2,          0,          3,          1,          0,         50
14,  2,  7,  6,        304,        315,        141,         52,        342,        247,        145,         26,         28,          4,          0,          2,          1,       1606
6,  2,  3,  9,        310,        324,        134,         50,        288,        320,        154,         53,         35,          1,          1,          4,          1,       1674
3,  2,  6,  9,       2171,       2195,       1018,        304,       2336,       2163,       1090,        445,         82,         31,          6,          0,          3,      11845
14,  2,  7,  5,       7184,       7287,       3484,       1198,       7724,       6948,       3192,       1075,        281,         38,          9,          0,          0,      38421
```
• Posts: 2,077
xoroshiro32++ zfreq distributions:
```
# Zero run frequency

# Actual
# a,  b,  c,  d,   mean run,     zfreq1,     zfreq2,     zfreq3,     zfreq4,     zfreq5,     zfreq6,     zfreq7,     zfreq8,     zfreq9,    zfreq10,    zfreq11,    zfreq12,    zfreq13,    zfreq14,    zfreq15,    zfreq16,    zfreq17,    zfreq18,    zfreq19,    zfreq20,    zfreq21
# ideal  , , , , 1.58197671,  631342768,  232258025,   85442952,   31432706,   11563446,    4253954,    1564942,     575710,     211792,      77914,      28663,      10544,       3879,       1427,        525,        193,         71,         26,         10,          4,          1
# scro   , , , , 1.58199635,  631325497,  232246374,   85451022,   31434743,   11560489,    4254398,    1565717,     576225,     211365,      77684,      28938,      10692,       3807,       1451,        510,        212,         63,         30,         21,          7,          1
13,  5, 10,  9, 1.58240278,  631068452,  232245039,   85428827,   31471299,   11583389,    4264295,    1572133,     579737,     212366,      78766,      28980,      10799,       3953,       1534,        532,        202,         69,         26,          6,          4,          3
13,  5,  8, 10, 1.58158174,  631742055,  232221020,   85459333,   31403138,   11552349,    4245117,    1562003,     574624,     211339,      78152,      28716,      10682,       3985,       1412,        506,        177,         80,         22,          9,          5,          1
14,  2,  7,  6, 1.58153314,  631280667,  232302588,   85419904,   31394728,   11532296,    4230888,    1552946,     569943,     207581,      75934,      27833,      10138,       3657,       1397,        516,        202,         70,         29,          7,          5,          4
6,  2,  3,  9, 1.58233612,  631080306,  232610061,   85557191,   31490618,   11553432,    4242365,    1553124,     569770,     208316,      76330,      27898,      10017,       3742,       1371,        493,        157,         61,         19,          7,          5,          0
3,  2,  6,  9, 1.57931659,  632461351,  232337522,   85228196,   31250505,   11425900,    4175966,    1525198,     556161,     202255,      73738,      26697,       9772,       3564,       1238,        492,        160,         53,         36,          8,          2,          2
14,  2,  7,  5, 1.57728590,  633209074,  232494821,   85032136,   31096279,   11317144,    4114211,    1492729,     541039,     195269,      70772,      25843,       9337,       3404,       1195,        418,        142,         50,         17,          9,          3,          1

# |Actual-Ideal|^2/Ideal
# a,  b,  c,  d,     zfreq1,     zfreq2,     zfreq3,     zfreq4,     zfreq5,     zfreq6,     zfreq7,     zfreq8,     zfreq9,    zfreq10,    zfreq11,    zfreq12,    zfreq13,    zfreq14,    zfreq15,    zfreq16,    zfreq17,    zfreq18,    zfreq19,    zfreq20,    zfreq21,      total
# ideal  , , , ,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0
# scro   , , , ,          0,          1,          1,          0,          1,          0,          0,          0,          1,          1,          3,          2,          1,          0,          0,          2,          1,          1,         12,          2,          0,         30
13,  5, 10,  9,        119,          1,          2,         47,         34,         25,         33,         28,          2,          9,          4,          6,          1,          8,          0,          0,          0,          0,          2,          0,          4,        327
13,  5,  8, 10,        253,          6,          3,         28,         11,         18,          6,          2,          1,          1,          0,          2,          3,          0,          1,          1,          1,          1,          0,          0,          0,        337
14,  2,  7,  6,          6,          9,          6,         46,         84,        125,         92,         58,         84,         50,         24,         16,         13,          1,          0,          0,          0,          0,          1,          0,          9,        624
6,  2,  3,  9,        109,        534,        153,        107,          9,         32,         89,         61,         57,         32,         20,         26,          5,          2,          2,          7,          1,          2,          1,          0,          1,       1250
3,  2,  6,  9,       1982,         27,        540,       1056,       1636,       1430,       1009,        664,        429,        224,        135,         57,         26,         25,          2,          6,          5,          4,          0,          1,          1,       9258
14,  2,  7,  5,       5517,        241,       1975,       3601,       5246,       4591,       3332,       2088,       1289,        655,        277,        138,         58,         38,         22,         13,          6,          3,          0,          0,          0,      29092
```