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

Random/LFSR on P2

1646567697092

Comments

  • xoroshiro32++ nzfreq distributions:
    # Non-zero run frequency
    
    # Actual
    # a,  b,  c,  d,    nzfreq1,    nzfreq2,    nzfreq3,    nzfreq4,    nzfreq5,    nzfreq6,    nzfreq7,    nzfreq8,    nzfreq9,   nzfreq10,   nzfreq11,   nzfreq12,   nzfreq13,   nzfreq14,   nzfreq15,   nzfreq16,   nzfreq17,   nzfreq18,   nzfreq19,   nzfreq20,   nzfreq21,   nzfreq22,   nzfreq23,   nzfreq24,   nzfreq25,   nzfreq26,   nzfreq27,   nzfreq28,   nzfreq29,   nzfreq30,   nzfreq31,   nzfreq32,   nzfreq33,   nzfreq34,   nzfreq35,   nzfreq36,   nzfreq37,   nzfreq38,   nzfreq39,   nzfreq40,   nzfreq41,   nzfreq42,   nzfreq43,   nzfreq44,   nzfreq45
    # ideal  , , , ,  367426785,  232258025,  146815072,   92804826,   58663838,   37082618,   23440685,   14817339,    9366344,    5920659,    3742570,    2365756,    1495443,     945300,     597544,     377720,     238764,     150928,      95405,      60307,      38121,      24097,      15232,       9629,       6087,       3847,       2432,       1537,        972,        614,        388,        245,        155,         98,         62,         39,         25,         16,         10,          6,          4,          3,          2,          1,          1
    # scro   , , , ,  367409237,  232249822,  146806621,   92822979,   58653366,   37074317,   23448505,   14822833,    9366603,    5924351,    3742556,    2364557,    1495255,     945073,     597224,     376964,     238020,     151211,      95677,      60491,      37941,      24158,      15310,       9608,       6148,       3831,       2415,       1568,        998,        609,        350,        233,        154,        100,         64,         39,         19,         14,         13,          2,          6,          3,          0,          0,          0
     13,  5, 10,  9,  367302869,  232229119,  146718311,   92791823,   58677241,   37058196,   23440771,   14827097,    9386855,    5930327,    3748361,    2370708,    1497167,     948777,     596331,     378695,     238976,     150237,      95204,      60327,      37981,      24077,      15118,       9441,       6084,       3877,       2422,       1443,        958,        559,        384,        265,        149,         99,         63,         45,         16,         17,         10,          4,          5,          1,          2,          1,          0
     13,  5,  8, 10,  367728518,  232245257,  146926702,   92831430,   58671183,   37048415,   23422648,   14800711,    9356825,    5911291,    3728654,    2360936,    1491313,     942907,     598681,     377659,     239656,     151441,      95704,      60200,      38343,      24248,      15283,       9727,       6297,       3884,       2476,       1527,       1008,        632,        429,        250,        167,        114,         80,         34,         35,         14,         19,         11,          6,          2,          2,          3,          1
     14,  2,  7,  6,  366965447,  232196581,  146899946,   92933989,   58751154,   37115343,   23480920,   14844922,    9379980,    5917108,    3739034,    2357498,    1487161,     939631,     592680,     374313,     235313,     148666,      93244,      58621,      36874,      23345,      14660,       9233,       5909,       3658,       2238,       1501,        865,        567,        355,        216,        132,         83,         53,         33,         33,          9,          5,          6,          5,          1,          0,          1,          1
      6,  2,  3,  9,  367262668,  232459900,  146904878,   93009628,   58728062,   37146715,   23417722,   14792621,    9325870,    5884690,    3710407,    2344103,    1478255,     930842,     588180,     369176,     233383,     147006,      92909,      58418,      36917,      23373,      14571,       9360,       5806,       3677,       2279,       1428,        884,        599,        346,        250,        149,         80,         44,         29,         21,         15,         10,          5,          4,          1,          1,          1,          0
      3,  2,  6,  9,  367070236,  232470768,  147003686,   93103995,   58811590,   37167145,   23473097,   14838603,    9362515,    5906730,    3721886,    2347726,    1479220,     933532,     587394,     370190,     233216,     146689,      92652,      58532,      36805,      23199,      14667,       9202,       5667,       3678,       2331,       1427,        954,        555,        335,        221,        132,         96,         49,         40,         22,          9,          7,          6,          4,          4,          1,          0,          2
     14,  2,  7,  5,  366630182,  232707119,  147186899,   93300812,   58962067,   37256749,   23469303,   14839920,    9346694,    5897542,    3706995,    2335772,    1472526,     925241,     579797,     366544,     230456,     145011,      90467,      57187,      35945,      22641,      14170,       8800,       5508,       3582,       2131,       1433,        883,        555,        368,        225,        131,         78,         54,         35,         33,         16,          9,          5,          4,          0,          1,          3,          0
    
    # |Actual-Ideal|^2/Ideal
    # a,  b,  c,  d,    nzfreq1,    nzfreq2,    nzfreq3,    nzfreq4,    nzfreq5,    nzfreq6,    nzfreq7,    nzfreq8,    nzfreq9,   nzfreq10,   nzfreq11,   nzfreq12,   nzfreq13,   nzfreq14,   nzfreq15,   nzfreq16,   nzfreq17,   nzfreq18,   nzfreq19,   nzfreq20,   nzfreq21,   nzfreq22,   nzfreq23,   nzfreq24,   nzfreq25,   nzfreq26,   nzfreq27,   nzfreq28,   nzfreq29,   nzfreq30,   nzfreq31,   nzfreq32,   nzfreq33,   nzfreq34,   nzfreq35,   nzfreq36,   nzfreq37,   nzfreq38,   nzfreq39,   nzfreq40,   nzfreq41,   nzfreq42,   nzfreq43,   nzfreq44,   nzfreq45,      total
    # ideal  , , , ,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0,          0
    # scro   , , , ,          1,          0,          0,          4,          2,          2,          3,          2,          0,          2,          0,          1,          0,          0,          0,          2,          2,          1,          1,          1,          1,          0,          0,          0,          1,          0,          0,          1,          1,          0,          4,          1,          0,          0,          0,          0,          1,          0,          1,          3,          1,          0,          2,          1,          1,         41
     13,  5, 10,  9,         42,          4,         64,          2,          3,         16,          0,          6,         45,         16,          9,         10,          2,         13,          2,          3,          0,          3,          0,          0,          1,          0,          1,          4,          0,          0,          0,          6,          0,          5,          0,          2,          0,          0,          0,          1,          3,          0,          0,          1,          0,          1,          0,          0,          1,        266
     13,  5,  8, 10,        248,          1,         85,          8,          1,         32,         14,         19,         10,         15,         52,         10,         11,          6,          2,          0,          3,          2,          1,          0,          1,          1,          0,          1,          7,          0,          1,          0,          1,          1,          4,          0,          1,          3,          5,          1,          4,          0,          8,          4,          1,          0,          0,          4,          0,        567
     14,  2,  7,  6,        579,         16,         49,        180,        130,         29,         69,         51,         20,          2,          3,         29,         46,         34,         40,         31,         50,         34,         49,         47,         41,         23,         21,         16,          5,          9,         15,          1,         12,          4,          3,          3,          3,          2,          1,          1,          3,          3,          2,          0,          0,          1,          2,          0,          0,       1662
      6,  2,  3,  9,         73,        175,         55,        452,         70,        111,         22,         41,        175,        219,        276,        198,        198,        221,        147,        193,        121,        102,         65,         59,         38,         22,         29,          8,         13,          8,         10,          8,          8,          0,          5,          0,          0,          3,          5,          3,          1,          0,          0,          0,          0,          1,          0,          0,          1,       3137
      3,  2,  6,  9,        346,        195,        242,        964,        372,        193,         45,         31,          2,         33,        114,        137,        176,        146,        172,        150,        129,        119,         79,         52,         45,         33,         21,         19,         29,          7,          4,          8,          0,          6,          7,          2,          3,          0,          3,          0,          0,          3,          1,          0,          0,          0,          0,          1,          1,       3895
     14,  2,  7,  5,       1727,        868,        942,       2651,       1516,        818,         35,         34,         41,         90,        338,        380,        351,        426,        527,        331,        289,        232,        256,        161,        124,         88,         74,         71,         55,         18,         37,          7,          8,          6,          1,          2,          4,          4,          1,          0,          3,          0,          0,          0,          0,          3,          0,          4,          1,      12526
    
  • evanhevanh Posts: 15,126
    LOL, it ran in 25 seconds! There ain't many with b=1.
      1  1 14
     14  1  1
      2  1  5
      5  1  2
      5  1 14
     14  1  5
      7  1 12
     12  1  7
      8  1  9
      9  1  8
    
  • evanh wrote: »
    LOL, it ran in 25 seconds! There ain't many with b=1.
      1  1 14
     14  1  1
      2  1  5
      5  1  2
      5  1 14
     14  1  5
      7  1 12
     12  1  7
      8  1  9
      9  1  8
    

    That's the same number with b=1 as xoroshiro. How many altogether?
  • evanhevanh Posts: 15,126
    Okay, full list is decent:
      1  1 14
     14  1  1
      2  1  5
      5  1  2
      5  1 14
     14  1  5
      7  1 12
     12  1  7
      8  1  9
      9  1  8
      2  2  7
      7  2  2
      2  2  9
      9  2  2
      5  2 10
     10  2  5
      6  2  9
      9  2  6
      8  2 15
     15  2  8
      9  2 14
     14  2  9
     10  2 11
     11  2 10
     10  2 13
     13  2 10
      1  3 10
     10  3  1
      2  3  3
      3  3  2
      5  3  6
      6  3  5
      6  3 13
     13  3  6
      1  4  4
      4  4  1
      3  5  6
      6  5  3
      3  5  8
      8  5  3
      1  6 14
     14  6  1
      1  7  8
      8  7  1
      1  7 12
     12  7  1
      5  7  6
      6  7  5
      2  8  7
      7  8  2
      4  8  5
      5  8  4
      9  8 14
     14  8  9
     11  8 12
     12  8 11
      3  9  8
      8  9  3
      7  9 14
     14  9  7
      3 10  4
      4 10  3
      4 10  5
      5 10  4
      6 10  9
      9 10  6
      2 11  3
      3 11  2
      2 11  5
      5 11  2
      2 11 13
     13 11  2
     13 11 14
     14 11 13
      2 12  3
      3 12  2
      2 13  3
      3 13  2
      4 14 11
     11 14  4
      5 14 10
     10 14  5
      8 15  9
      9 15  8
    
  • Same total as xoroshiro, 42 mirror pairs. Manual labour in the sunshine beckons.
  • evanhevanh Posts: 15,126
    This'll take 16 hours to produce distributions for all full-period cases. I'll report back in the morning.
  • evanhevanh Posts: 15,126
    Lol, it's 2 AM here. Sometime during daylight then.
  • I sleep for a few hours and find the gears have been turning.
    The number of candidates mirrors xoroshiro, which makes sense.
    Then the only hope is that the escape-from-zero benefit of the NOT operation would improve other statistics by-proxy.
    I guess that is very possible with the right candidate... I'll give it a much better than 50% chance, but then could be higher with the NOT and either '<< B' or '>> B'.
    Thanks for digging into this.
  • TonyB_ wrote: »
    I think the best name is xoroshironot as that describes the algorithm: xor, rotate, shift, rotate, not. Thus xoroshironot32++ [5,1,14,9].
    Technically, yes, but I was trying to steer clear of that exact name, as I already have published it for the (superior in many ways) three-state-variable version of my xoroshiro++ variant.
    However, I already documented the alias for it as Xoroshiroppm, which would allow me to abandon XoroshiroNOT in favor of this new variant, if necessary.
    Let us see how this pans out first.
  • evanhevanh Posts: 15,126
    It's a little over half way through so here's what's done so far.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-04-02 04:25
    I notice a snag, that although it might really be just an annoyance, might add excess burden to the already stressed output scrambler, if it were addressed...

    Normally xoroshiro32 would emit 65535 zeros, but 65536 of all other values due to the 2^N-1 period (which has the negative consequence of creating an excess of set bits over the entire period).
    Haphazardly inverting bits (i.e. 'Not') would shift the short value from zero to something else.
    That might be problematic in the case that some 'aware' software assumes only the missing zero, so intentionally discards them, for example.
    If that issue needed to be addressed, then the final output would have to be xor'd with the missing value to restore the missing zero, at the end of the output calculation.
    Or, perhaps, on-the-fly as the register output is accessed.

    On the plus side, if the missing output value were not xor'd with each output, and it happened to be one that contains exactly 8 set bits, then the total 0/1 bit balance would be perfect over the entire period (therefore over the course of an arbitrary number of full periods cycles). That behavior would be ideal for those writing software that flips a lot of coins.

    If this makes your head spin... keep the status quo.
  • evanhevanh Posts: 15,126
    I thought the idea was that zero became part of the engine period, ie: 2^N.
  • evanhevanh Posts: 15,126
    Heh, which would mess up the distribution runs a little. Since they're still crafted for 2^N - 1.
  • evanhevanh Posts: 15,126
    Here's the complete set of frequency distribution output.
  • TonyB_TonyB_ Posts: 2,105
    edited 2019-04-02 12:45
    Thanks for doing the tests, Evan.

    Looking just at pfreq for closest candidates to ideal pfreq0 = pfreq1 = 1580030169
    (see http://forums.parallax.com/discussion/comment/1468197/#Comment_1468197)
    here are the best ones:
     a  b  c  d		pfreq0		pfreq1
    ideal, , , ,		1580030169	1580030169
     2, 2, 7, 2,		1580023328,	1580025564,
     2, 3, 3, 4,		15801.....,	15799.....,
     3, 3, 2,12,		1580083409,	1579966328,
     3,11, 2,10,		1579992577,	1580058527,
     3,13, 2, 9,		15801.....,	15798.....,
     6, 2, 9, 1,		1580006815,	1580021051,
     6, 5, 3, 2,		1579998292,	1580085834,
     7, 2, 2, 3,		1580062718,	1579992030,
     7, 2, 2, 6,		1580050663,	1579992706,
     8, 1, 9, 4,		15799.....,	15801.....,
     8, 1, 9,12,		1579983051,	1580053935,
    13, 3, 6, 4,		1580013113,	1580037432,
    14,11,13,10,		1579990608,	1580083846,
    

    I need to search for my program that reads the binary files and outputs Chi-Square results.

    EDIT:
    For comparison, here are the corresponding values for xoroshiro32++ [13,5,10,9] in P2 rev. B:
     a  b  c  d		pfreq0		pfreq1
    ideal, , , ,		1580030169	1580030169,
    13, 5,10, 9,		1580109068,	1579940482,
    
  • PractRand tests on the ten candidates above with full values could be useful.
  • evanhevanh Posts: 15,126
    The good news is there is a couple of good B=1 candidates right there.

    However, it sounds like idea about including zero in the full period is flawed. I think it's worse than expected, as in zero becomes part of the full period but something else is removed. Possibly -1.

  • evanhevanh Posts: 15,126
    I've just been doing some alternative full-period searches:
    - When looking for 2^N states as full-period the output is nothing.
    - But when looking for 2^N - 1 states as full-period and with s0=0 and s1=0 as start and finish conditions then I get the very same 84 triplets.
  • TonyB_TonyB_ Posts: 2,105
    edited 2019-04-02 12:54
    evanh wrote: »
    The good news is there is a couple of good B=1 candidates right there.

    However, it sounds like idea about including zero in the full period is flawed. I think it's worse than expected, as in zero becomes part of the full period but something else is removed. Possibly -1.

    Why is B=1 so important? Other values give better pfreq. I haven't looked at any others, but [8,1,9,4] is not very good on zfreq and nzfreq.

    An XOR at the end, as already suggested, to make the zero frequency one fewer than the non-zero would be simple, at the cost of an extra instruction.

    P.S.
    Earlier reply edited to add chosen xoroshiro32++ values
    http://forums.parallax.com/discussion/comment/1468260/#Comment_1468260
  • evanhevanh Posts: 15,126
    edited 2019-04-02 13:18
    I'm just following the path Chris (Xoroshironot) is on. B=1 was one of the criteria, part of the Gray Code function. Also, I thought the inversion made zero frequency one more not one less. I've proven an all zero state repeats every 2^N - 1.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-04-02 15:33
    evanh wrote: »
    I think it's worse than expected, as in zero becomes part of the full period but something else is removed. Possibly -1.
    I don't think -1 can be removed, since the 'Not' isn't used on all occurences of 's1'.
    Removal of a single zero is a common convention, but in the vast majority of use cases it is not relevant which value is removed.
    If I could choose, I would remove an occurrence of 0x5555. That would maintain bit balance over the entire stream (and I like that value less than I do zero).
    The fact that any stream is short by the omission of a single value occurrence is only a consideration for smaller state generators.
    evanh wrote: »
    When looking for 2^N states as full-period the output is nothing.
    Unfortunately, 2^N period is not possible with a vanilla LFSR.
    I am still working to solve that with something more eloquent than other alternatives.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-04-02 16:05
    evanh wrote: »
    The good news is there is a couple of good B=1 candidates right there.
    B=1 seems rational to me, but that does not make it correct in the context of what you are trying to do, and the fact that 'rational' does always fit with PRNGs.
    At the time I did not understand your use of specific criteria on the full period to steer the statistics toward the behavior of a larger state generator (per Scro).
    Seba made some comment critical of that, but as long as the end result is a stream that also pushes against ~1GB in PractRand (and passes Small Crush), all is well.
    As I recall, if I hash x and y independently before passing them to the ++ scrambler, I can always get to 1GB in Practrand (with options -tf 2 -te 1), but never to 2GB.
    Thus my comment about 'status quo', as it might be difficult to squeeze enough net improvement to make the effort worthwhile.
  • evanh wrote: »
    But when looking for 2^N - 1 states as full-period and with s0=0 and s1=0 as start and finish conditions then I get the very same 84 triplets.
    That illustrates another negative facet of lacking a missing zero... there must exist a seed state that will result in one iteration leaving the state untouched.
    When that bad seed state is zero, as in the normal xoroshiro, you only need to ensure at least one bit is set when seeding.
    With the 'Not' applied, you must xor each non-zero seed with the known bad seed value before storing the seed in the state.
    Finding the bad seed (even by brute force) is fairly trivial for a 32-bit state generator.
    Properly seeding is also trivial once the bad seed is known, as this is already being done with the normal xoroshiro (to avoid all zeros).
  • evanh wrote: »
    But when looking for 2^N - 1 states as full-period and with s0=0 and s1=0 as start and finish conditions then I get the very same 84 triplets.
    That illustrates another negative facet of lacking a missing zero... there must exist a seed state that will result in one iteration leaving the state untouched.
    When that bad seed state is zero, as in the normal xoroshiro, you only need to ensure at least one bit is set when seeding.
    With the 'Not' applied, you must xor each non-zero seed with the known bad seed value before storing the seed in the state.
    Finding the bad seed (even by brute force) is fairly trivial for a 32-bit state generator.
    Properly seeding is also trivial once the bad seed is known, as this is already being done with the normal xoroshiro (to avoid all zeros).

    I see what you mean now. Inversion only applies to s0, though, so setting one bit in s1 should guarantee a good seed?
  • TonyB_TonyB_ Posts: 2,105
    edited 2019-04-02 15:43
    deleted
  • TonyB_ wrote: »
    I see what you mean now. Inversion only applies to s0, though, so setting one bit in s1 should guarantee a good seed?
    I'll look at calculating the 1 cycle seed value for any given ABC. The missing output value would depend on D, as well, and even if it wasn't used for output xor, would be necessary to know.
  • TonyB_ wrote: »
    I see what you mean now. Inversion only applies to s0, though, so setting one bit in s1 should guarantee a good seed?
    I'll look at calculating the 1 cycle seed value for any given ABC. The missing output value would depend on D, as well, and even if it wasn't used for output xor, would be necessary to know.

    Actually it's subtract we need for the output, not xor. To make sure the zero output frequency is 2^N-1, subtract the non-zero 2^N-1 value from each output.
  • TonyB_TonyB_ Posts: 2,105
    edited 2019-04-03 00:16
    Some [a,b,c,d] for the new engine have very good frequency distributions that are better than the chosen one in the P2. However, a good distribution does not imply a good score in PRNG tests, which I can't perform.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-04-03 04:10
    Currently my PractRand analysis finds about 4 of the above pfreq candidates possibly worth considering.
    However, the forward bits analysis is slightly worse and the reverse bits is slightly better (as compared to 13,5,10,9) on ALL of the 4 I liked.
    That is marginally suspicious.

    Presuming you concur... it seems the issue might be related to using '>>' instead of the original '<<'.
    I tried a few with '<<' instead and the balance between forward and reverse bits looked better.
    Perhaps (and very likely) Seba understands something here that is not obvious to me.
    Changing (back) to '<<' from '>>' (and keeping the NOT): A = 16 - A : B = (just) B : C = 16 - C
    This creates an entirely new set of streams, thus possible candidates with respect to ABC and D (since the shift direction change results in a subtle asymmetry, I believe).
    TonyB_ wrote: »
    Actually it's subtract we need for the output, not xor.
    That will work. I'm curious how each approach affects PractRand's FPF analysis... Initial check says some effect, but not very much.
  • xoroshironotxoroshironot Posts: 309
    edited 2019-04-03 14:14
    Switching the shift back to '<<' (so now only a Not has been added to the original code), takes us back to the pre-Not constants, since xor, rotate and shift are unaffected by that change.

    As a result, this yields an easy example... your original [13,5,10,9], with these properties:
    1. Very similar PractRand results to original.
    2. Excellent escape from zero properties (10 iterations, in avg. bits set in output word considering all 32 single-set-bit seeds, no output subtraction):
    Original 1.5 5.375 6.96875 7.96875 8.75 8.1875 7.46875 8.6875 8.375 8.5
    NOT << 1.5 9.71875 7.96875 7.84375 8.46875 7.3125 9.0625 7.8125 8.0625 7.9375
    3. Likely same, or very similar pf, zrf, and nzrf statistics... would need tested (and again with output correction below, if it will be used, just to verify).
    4. Must subtract (or xor) 0x3BE1 from output to restore missing zero, if having one less zero output (as original) is required.
    5. Must subtract (or xor) these values when non-zero seeding: s[0] = s[0]_seed - 0x2034, s[1]= s[1]_seed - 0xB659

    So much effort for so little of a change to code... likely not worth the effort except for #2 and/or if there is some improvement in testing #3.
Sign In or Register to comment.