Shop OBEX P1 Docs P2 Docs Learn Events
Random/LFSR on P2 - Page 66 — Parallax Forums

Random/LFSR on P2

1636466686992

Comments

  • evanhevanh Posts: 15,126
    -s1 is a sum.
  • evanhevanh Posts: 15,126
    Oh, oops, it's not a negative, the squiggly is just another xor.
  • evanhevanh Posts: 15,126
    Huh, so, an integer shifted right by 1 and xor'd with -1 produces the Gray coded value, correct?
  • xoroshironotxoroshironot 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.
  • xoroshironotxoroshironot 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.
  • evanhevanh Posts: 15,126
    Whereas Gray Code would be simply:
    s1 ^ (s1 >> 1)
    
    I had no idea it was that few steps! How cool.
  • evanhevanh Posts: 15,126
    @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.
  • evanhevanh Posts: 15,126
    Kind of pointless having the higher res when all you end up doing is increasing the font size. Sigh.

  • evanhevanh Posts: 15,126
    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.
  • evanhevanh Posts: 15,126
    x + 5 * y might achieve both.
  • xoroshironotxoroshironot 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. :smile:
    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.
  • xoroshironotxoroshironot 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.
  • evanhevanh Posts: 15,126
    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.
  • xoroshironotxoroshironot 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.
  • evanhevanh Posts: 15,126
    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.
  • 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.
  • evanhevanh Posts: 15,126
    Cool. I'll see about getting out the old code and doing some pair distribution runs for you ...
  • What are the full-length candidates for this new engine?
  • evanhevanh Posts: 15,126
    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
    
  • TonyB_TonyB_ Posts: 2,105
    edited 2019-04-01 11:16
    deleted
  • evanhevanh Posts: 15,126
    I've called the new one Xorograyro32++. With parameters of [5 1 14 9]. Same seed of 1.

  • evanhevanh Posts: 15,126
    Here's the distribution for Xorograyro32++ [5 1 14 9]. pdist total is spot on. zdist and nzdist totals are a little out.
  • evanhevanh Posts: 15,126
    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.
  • Evan, sorry, I misread the C constant and I do agree with your values.
  • TonyB_TonyB_ Posts: 2,105
    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].
  • 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.
  • evanhevanh Posts: 15,126
    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 ...

  • 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 ...
  • 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
    
  • 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
    
Sign In or Register to comment.