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

Random/LFSR on P2

1424345474892

Comments

  • Heater.Heater. Posts: 21,230
    edited 2018-05-02 06:56
    Cheap too, only 60 something dollars on godaddy.
  • evanhevanh Posts: 15,091
    edited 2018-05-02 01:50
    TonyB_ wrote: »
    ... My PC isn't up to the job as 4 Gbytes of RAM would be needed ...
    If DRAM prices hadn't gone through the roof in the last year or so I'd be telling you it's time to get more.
    I've tested xoroshiro16++ and the frequency distribution of 16-bit pairs is close to the binomial for the best quadruples, which confirms that xoroshiro++ is not 2-dimensionally equidistributed.
    What code can you show me. I'm struggling to grok your descriptions.

  • evanh wrote: »
    TonyB_ wrote: »
    ... My PC isn't up to the job as 4 Gbytes of RAM would be needed ...
    If DRAM prices hadn't gone through the roof in the last year or so I'd be telling you it's time to get more.
    I've tested xoroshiro16++ and the frequency distribution of 16-bit pairs is close to the binomial for the best quadruples, which confirms that xoroshiro++ is not 2-dimensionally equidistributed.
    What code can you show me. I'm struggling to grok your descriptions.

    My PC has all the RAM it can take and it's much less than 4GB!
    Program sent by PM (and you'll know why when you see it).
  • evanhevanh Posts: 15,091
    Here we go. I've used the exact same xoro source I have from the automated testing, it doesn't handle D==0.
  • evanhevanh Posts: 15,091
    Here's a piccy of the runs showing CPU loading of one thread max'd out (6.25%) and the 4 GB allocation bump. Each one is 73 seconds long.

    Screenshot_20180504_030144.png
    728 x 593 - 50K
  • evanhevanh Posts: 15,091
    Right, after a bug fix in the for() loops and more checking/clean up, here's the corrected reports:
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-05 00:52
    evanh wrote: »
    Right, after a bug fix in the for() loops and more checking/clean up, here's the corrected reports:

    Many thanks for running the pair frequency tests, Evan. I think there is a tiny error in the code and this
    	// read pair array and increment freq values
    	for( irng = 0; irng < (1UL<<32)-1; irng++ )  freqs[pairs[irng]]++;
    

    misses out the FFFF_FFFF pair and it should be
    	// read pair array and increment freq values
    	for( irng = 0; irng < (1UL<<32); irng++ )  freqs[pairs[irng]]++;
    

    I've run a program to find the frequencies of the FFFF_FFFF pairs and add them to your data, so there is no need for you to run the tests again.
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-10-01 12:48
    From Evan's tests:

    Pair frequencies for xoroshiro32++ [14,2,7,d]
    Actual values and Expected binomial
    # a,  b,  c,  d,         f0,         f1,         f2,         f3,         f4,         f5,         f6,         f7,         f8,         f9,        f10,        f11,        f12,        f13,        f14,        f15,        f16,        f17,        f18,        f19
     14,  2,  7,  0, 1584664130, 1574310324,  789171375,  264234093,   66464183,   13438566,    2290398,     341358,      46243,       5818,        715,         86,          7,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7,  1, 1575680423, 1584386273,  792180409,  262616859,   64926397,   12769204,    2079966,     288613,      34863,       3891,        371,         26,          0,          1,          0,          0,          0,          0,          0,          0
     14,  2,  7,  2, 1568230668, 1591902671,  795888795,  261281644,   63375117,   12107094,    1897698,     252312,      28211,       2783,        278,         23,          2,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7,  3, 1576741668, 1583323566,  791644486,  262804532,   65146642,   12863771,    2107269,     295459,      35622,       3908,        333,         35,          4,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7,  4, 1575995203, 1584081205,  792028698,  262650289,   64981545,   12806256,    2092336,     292296,      35345,       3736,        357,         25,          3,          0,          1,          0,          0,          0,          0,          0
     14,  2,  7,  5, 1576661052, 1583423321,  791674049,  262776786,   65121487,   12864448,    2110786,     295138,      35867,       3945,        372,         41,          3,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7,  6, 1579336929, 1580735764,  790348643,  263221421,   65684445,   13109945,    2176642,     310656,      38143,       4228,        446,         32,          1,          1,          0,          0,          0,          0,          0,          0
     14,  2,  7,  7, 1577009081, 1583053081,  791531858,  262821569,   65207109,   12891277,    2117255,     295752,      36082,       3820,        383,         26,          2,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7,  8, 1699319755, 1462572382,  734015615,  277326305,   88015114,   24931625,    6574423,    1661540,     412910,     102946,      25675,       6617,       1746,        461,        137,         34,          8,          0,          1,          1
     14,  2,  7,  9, 1574674599, 1585407863,  792662675,  262453905,   64713907,   12674899,    2056612,     284558,      34275,       3605,        361,         33,          4,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7, 10, 1580342637, 1579739886,  789850938,  263359222,   65902320,   13205283,    2206608,     316036,      39522,       4382,        418,         38,          5,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7, 11, 1577315879, 1582758316,  791339517,  262908594,   65267816,   12915314,    2122195,     298985,      36293,       3973,        381,         31,          1,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7, 12, 1581527887, 1578547305,  789242532,  263591462,   66151392,   13305026,    2233546,     322292,      40705,       4652,        457,         36,          4,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7, 13, 1580534363, 1579574938,  789701738,  263415458,   65948836,   13216977,    2213107,     316861,      40077,       4460,        431,         45,          4,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7, 14, 1579659531, 1580409000,  790172195,  263301877,   65756857,   13128926,    2185109,     310158,      38822,       4373,        414,         29,          3,          1,          0,          1,          0,          0,          0,          0
     14,  2,  7, 15, 1580238431, 1579800409,  789931280,  263385199,   65872856,   13184111,    2197712,     313292,      39160,       4350,        443,         50,          2,          0,          0,          0,          0,          0,          0,          0
    #binomial, , , , 1580030169, 1580030169,  790015084,  263338361,   65834590,   13166918,    2194486,     313498,      39187,       4354,        435,         40,          3,          0,          0,          0,          0,          0,          0,          0
    

    All other frequencies not shown = 0
    f0*0 + f1*1 + f2*2 + f3*3 + ... = 2^32-1 = full period
    f0 + f1 + f2 + f3 + ... = 2^32-1 or 2^32

    |Actual-Expected| values
    # a,  b,  c,  d,         f0,         f1,         f2,         f3,         f4,         f5,         f6,         f7,         f8,         f9,        f10,        f11,        f12,        f13,        f14,        f15,        f16,        f17,        f18,        f19
     14,  2,  7,  0,    4633961,    5719845,     843709,     895732,     629593,     271648,      95912,      27860,       7056,       1464,        280,         46,          4,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7,  1,    4349746,    4356104,    2165325,     721502,     908193,     397714,     114520,      24885,       4324,        463,         64,         14,          3,          1,          0,          0,          0,          0,          0,          0
     14,  2,  7,  2,   11799501,   11872502,    5873711,    2056717,    2459473,    1059824,     296788,      61186,      10976,       1571,        157,         17,          1,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7,  3,    3288501,    3293397,    1629402,     533829,     687948,     303147,      87217,      18039,       3565,        446,        102,          5,          1,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7,  4,    4034966,    4051036,    2013614,     688072,     853045,     360662,     102150,      21202,       3842,        618,         78,         15,          0,          0,          1,          0,          0,          0,          0,          0
     14,  2,  7,  5,    3369117,    3393152,    1658965,     561575,     713103,     302470,      83700,      18360,       3320,        409,         63,          1,          0,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7,  6,     693240,     705595,     333559,     116940,     150145,      56973,      17844,       2842,       1044,        126,         11,          8,          2,          1,          0,          0,          0,          0,          0,          0
     14,  2,  7,  7,    3021088,    3022912,    1516774,     516792,     627481,     275641,      77231,      17746,       3105,        534,         52,         14,          1,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7,  8,  119289586,  117457787,   55999469,   13987944,   22180524,   11764707,    4379937,    1348042,     373723,      98592,      25240,       6577,       1743,        461,        137,         34,          8,          0,          1,          1
     14,  2,  7,  9,    5355570,    5377694,    2647591,     884456,    1120683,     492019,     137874,      28940,       4912,        749,         74,          7,          1,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7, 10,     312468,     290283,     164146,      20861,      67730,      38365,      12122,       2538,        335,         28,         17,          2,          2,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7, 11,    2714290,    2728147,    1324433,     429767,     566774,     251604,      72291,      14513,       2894,        381,         54,          9,          2,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7, 12,    1497718,    1482864,     772552,     253101,     316802,     138108,      39060,       8794,       1518,        298,         22,          4,          1,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7, 13,     504194,     455231,     313346,      77097,     114246,      50059,      18621,       3363,        890,        106,          4,          5,          1,          0,          0,          0,          0,          0,          0,          0
     14,  2,  7, 14,     370638,     378831,     157111,      36484,      77733,      37992,       9377,       3340,        365,         19,         21,         11,          0,          1,          0,          1,          0,          0,          0,          0
     14,  2,  7, 15,     208262,     229760,      83804,      46838,      38266,      17193,       3226,        206,         27,          4,          8,         10,          1,          0,          0,          0,          0,          0,          0,          0
    

    |Actual-Expected|/Expected values
    # a,  b,  c,  d,         f0,         f1,         f2,         f3,         f4,         f5,         f6,         f7,         f8,         f9,        f10,        f11,        f12
     14,  2,  7,  0, 0.00293283, 0.00362008, 0.00106796, 0.00340144, 0.00956325, 0.02063109, 0.04370590, 0.08886819, 0.18005971, 0.33624253, 0.64367816, 1.15000000, 1.33333333
     14,  2,  7,  1, 0.00275295, 0.00275697, 0.00274086, 0.00273982, 0.01379507, 0.03020555, 0.05218534, 0.07937849, 0.11034271, 0.10633899, 0.14712643, 0.35000000, 1.00000000
     14,  2,  7,  2, 0.00746789, 0.00751409, 0.00743493, 0.00781016, 0.03735837, 0.08049142, 0.13524260, 0.19517189, 0.28009288, 0.36081763, 0.36091954, 0.42500000, 0.33333333
     14,  2,  7,  3, 0.00208129, 0.00208438, 0.00206249, 0.00202716, 0.01044964, 0.02302338, 0.03974370, 0.05754103, 0.09097404, 0.10243454, 0.23448275, 0.12500000, 0.33333333
     14,  2,  7,  4, 0.00255372, 0.00256389, 0.00254882, 0.00261288, 0.01295739, 0.02739152, 0.04654848, 0.06763041, 0.09804271, 0.14193844, 0.17931034, 0.37500000, 0.00000000
     14,  2,  7,  5, 0.00213231, 0.00214752, 0.00209991, 0.00213252, 0.01083173, 0.02297196, 0.03814104, 0.05856496, 0.08472197, 0.09393661, 0.14482758, 0.02500000, 0.00000000
     14,  2,  7,  6, 0.00043875, 0.00044657, 0.00042221, 0.00044406, 0.00228064, 0.00432698, 0.00813128, 0.00906544, 0.02664148, 0.02893890, 0.02528735, 0.20000000, 0.66666666
     14,  2,  7,  7, 0.00191204, 0.00191319, 0.00191993, 0.00196246, 0.00953117, 0.02093435, 0.03519320, 0.05660642, 0.07923546, 0.12264584, 0.11954022, 0.35000000, 0.33333333
     14,  2,  7,  8, 0.07549829, 0.07433895, 0.07088405, 0.05311776, 0.33691292, 0.89350499, 1.99588286, 4.30000191, 9.53691275, 22.6440055, 58.0229885, 164.425000, 581.000000
     14,  2,  7,  9, 0.00338953, 0.00340353, 0.00335131, 0.00335862, 0.01702270, 0.03736781, 0.06282746, 0.09231318, 0.12534769, 0.17202572, 0.17011494, 0.17500000, 0.33333333
     14,  2,  7, 10, 0.00019776, 0.00018371, 0.00020777, 0.00007921, 0.00102879, 0.00291374, 0.00552384, 0.00809574, 0.00854875, 0.00643086, 0.03908045, 0.05000000, 0.66666666
     14,  2,  7, 11, 0.00171787, 0.00172664, 0.00167646, 0.00163199, 0.00860906, 0.01910879, 0.03294211, 0.04629375, 0.07385102, 0.08750574, 0.12413793, 0.22500000, 0.66666666
     14,  2,  7, 12, 0.00094790, 0.00093850, 0.00097789, 0.00096112, 0.00481209, 0.01048901, 0.01779915, 0.02805121, 0.03873733, 0.06844281, 0.05057471, 0.10000000, 0.33333333
     14,  2,  7, 13, 0.00031910, 0.00028811, 0.00039663, 0.00029276, 0.00173534, 0.00380187, 0.00848535, 0.01072734, 0.02271161, 0.02434542, 0.00919540, 0.12500000, 0.33333333
     14,  2,  7, 14, 0.00023457, 0.00023976, 0.00019887, 0.00013854, 0.00118073, 0.00288541, 0.00427298, 0.01065397, 0.00931431, 0.00436380, 0.04827586, 0.27500000, 0.00000000
     14,  2,  7, 15, 0.00013180, 0.00014541, 0.00010607, 0.00017786, 0.00058124, 0.00130577, 0.00147004, 0.00065710, 0.00068900, 0.00091869, 0.01839080, 0.25000000, 0.33333333
    

    Truncated to f0-f12 to avoid division by zero

    Comments
    [14,2,7,8] is the worst performer, as predicted by theory when d is exactly half the maximum possible rotation. The third table illustrates best how close most of the [a,b,c,d] quadruples are to the expected binomial, e.g. f0-f3 for [14,2,7,6] are each a better than 99.5% match and f1-f3 make up 92% of the total non-zero pair frequencies. Doing well in this test does not imply a quadruple will do the same in other tests.
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-06 01:30
    I emailed Melissa O'Neill about the new paper by David Blackman & Sebastiano Vigna announced on the forum here and this is her initial response:
    http://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.html
  • evanhevanh Posts: 15,091
    edited 2018-05-06 03:11
    Ouch, Melisa isn't impressed. :(

    I'm not convince her concerns are entirely valid for what we are wanting though:
    1: The progressiveness in state changes are hidden by the scrambler. That's the scrambler's job.
    2: Algorithmically predictable is a given. Not a concern to us. This isn't for cryptography.
    3: Invertible I don't understand. She seems focused on particular multipliers there. Maybe it's similar to predictability in that it can be hacked. I'm unsure how important this is, but it just sounds like it needs new constants. No shortage of those to choose from.

    EDIT: I guess when she read "all-purpose" she interpreted that to mean for cryptographic uses too.

  • Heater.Heater. Posts: 21,230
    I'm pretty sure Melisa does not include cryptographic quality when she says "all purpose".

    As far as I understand these things, which is very little, she is pointing out a serious problem as in:

    1) You have this PRNG whose output passses all maner of statistical tests of randomness. Which is sweet.

    2) But if you happen to multiply it's output by the wrong numbers in your application, which is something one is likely to do, what you up end up with fails those statistical tests pretty quickly. Not so sweet.

    I think I'll stick to JKISS32 :)


  • evanhevanh Posts: 15,091
    That's just a simple change to the multiplier value then isn't it. There's no shortage of options for what constants to choose from. No biggie there.

  • evanhevanh Posts: 15,091
    Tony and I are still searching for better constants to use here even.

  • Heater.Heater. Posts: 21,230
    evanh,
    That's just a simple change to the multiplier value then isn't it.
    That sounds like a question. I have no idea.
    There's no shortage of options for what constants to choose from. No biggie there.
    Might take a long while to try them all and see which works best.

    I thought the idea was use a multiplier that could be implemented as a couple of shifts and adds instead of an actual multiply. For the sake of speed. That would imply a multiplier with few 1 bits. In that case the search space for a better multiplier is much smaller.

    It's fascinating to watch these PRNG "wars". Even if I don't understand the details:

    Somebody dreams up a new PRNG.
    Somebody else dreams up a new statistical test or other technique to show how crappy it is.
    Rinse, repeat...

  • evanhevanh Posts: 15,091
    Next report for Tony - There's two versions of the numbers in the zdist_report, I think the first one is the correct one but that's not how the sudo-code was written. The second one is as per the sudo-code.

  • evanh wrote: »
    Next report for Tony - There's two versions of the numbers in the zdist_report, I think the first one is the correct one but that's not how the sudo-code was written. The second one is as per the sudo-code.

    Thanks, Evan. I must have made a mistake with the zero distribution code. I didn't refer back to my working x86 version. We need zdist for two quads, ideally [14,2,7,5] and [14,2,7,6], to see if there is any real difference.
  • evanhevanh Posts: 15,091
    edited 2018-05-06 13:48
    Here's those two plus a selection of six good ones from today's PR scores:
    Err, make that 4 + 4:
    __________________________________________________________________________________________________________
    
      Xoroshiro32(16)++ PractRand Score Table.  Build 2018-05-06 10:43:24 +1200
        PractRand v0.93 options: stdin -multithreaded -te 1 -tf 2 -tlmin 1KB
        Scoring ran from 2018-05-06 01:30:15 to 2018-05-06 10:35:19.  Double Full Period = 16 GB
    __________________________________________________________________________________________________________
                    Sampling apertures of the generator output, labelled as most to least bit-significance
      Candidate    ----------------------------------------------------------------------------------------
    [ A  B  C  D]  15:00 14:00 13:00 15:01 15:02  6:15  5:14  4:13  3:12  2:11  1:10  0:09 15:08 14:07 13:06 12:05 11:04 10:03  9:02  8:01  7:00
    ==========================================================================================================
    [ 5  2  6  9]     1G    4G    2G    2G    1G  512M    1G    2G    1G  256M  256M    1G    2G    2G    1G    1G    1G    2G    1G    1G    1G
    [ 6  2  5  9]     1G    4G    2G    4G    1G    1G    2G    2G    2G  512M  256M  512M    2G    1G  256M    1G    1G    1G    1G    1G    2G
    [14  2  7  5]   256M    4G    4G    2G    4G    1G    1G    1G    1G  512M  256M    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G
    [14  2  7  6]   512M    8G    2G    4G    2G  512M    1G    2G    1G    1G    1G    1G    2G    1G  256M  256M    2G  512M  512M  512M  512M
    
    [13  5 10 10]     1G    8G    4G    8G    2G  512M  512M  512M  512M  512M  512M  512M  512M    1G  512M  512M    1G    1G    1G  512M  512M
    [ 3  2  6  5]   512M    4G    2G    2G    2G    1G    1G    1G    1G    1G    1G    1G    1G  512M  512M  512M  512M    1G    1G    1G    1G
    [ 6  2  3  9]   512M    4G    2G    4G    2G    2G    2G    1G    2G    1G    1G    1G    1G    1G    1G    1G    1G  512M    1G    1G    1G
    [ 6  2 11  6]   512M    4G    2G    8G    2G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    2G    1G    1G    2G  512M    1G
    
  • evanhevanh Posts: 15,091
    Hehe, oops, I've spelt the Linux "sudo" command in place of pseudo. Didn't notice that before. I guess that shows my relative usages of the two.

  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-07 00:19
    evanh wrote: »
    Here's those two plus a selection of six good ones from today's PR scores:
    Err, make that 4 + 4:
    __________________________________________________________________________________________________________
    
      Xoroshiro32(16)++ PractRand Score Table.  Build 2018-05-06 10:43:24 +1200
        PractRand v0.93 options: stdin -multithreaded -te 1 -tf 2 -tlmin 1KB
        Scoring ran from 2018-05-06 01:30:15 to 2018-05-06 10:35:19.  Double Full Period = 16 GB
    __________________________________________________________________________________________________________
                    Sampling apertures of the generator output, labelled as most to least bit-significance
      Candidate    ----------------------------------------------------------------------------------------
    [ A  B  C  D]  15:00 14:00 13:00 15:01 15:02  6:15  5:14  4:13  3:12  2:11  1:10  0:09 15:08 14:07 13:06 12:05 11:04 10:03  9:02  8:01  7:00
    ==========================================================================================================
    [ 5  2  6  9]     1G    4G    2G    2G    1G  512M    1G    2G    1G  256M  256M    1G    2G    2G    1G    1G    1G    2G    1G    1G    1G
    [ 6  2  5  9]     1G    4G    2G    4G    1G    1G    2G    2G    2G  512M  256M  512M    2G    1G  256M    1G    1G    1G    1G    1G    2G
    [14  2  7  5]   256M    4G    4G    2G    4G    1G    1G    1G    1G  512M  256M    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G
    [14  2  7  6]   512M    8G    2G    4G    2G  512M    1G    2G    1G    1G    1G    1G    2G    1G  256M  256M    2G  512M  512M  512M  512M
    
    [13  5 10 10]     1G    8G    4G    8G    2G  512M  512M  512M  512M  512M  512M  512M  512M    1G  512M  512M    1G    1G    1G  512M  512M
    [ 3  2  6  5]   512M    4G    2G    2G    2G    1G    1G    1G    1G    1G    1G    1G    1G  512M  512M  512M  512M    1G    1G    1G    1G
    [ 6  2  3  9]   512M    4G    2G    4G    2G    2G    2G    1G    2G    1G    1G    1G    1G    1G    1G    1G    1G  512M    1G    1G    1G
    [ 6  2 11  6]   512M    4G    2G    8G    2G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    2G    1G    1G    2G  512M    1G
    

    In case others are interested, the sixteen columns beginning with 6:15 are PractRand scores for every possible contiguous 8-bit sample of the 16-bit output. The first number is the msb and the second the lsb, with wrapping around from bit 0 to bit 15 where necessary. No quadruples have all 16 scores of 1G or more and overall quadruple [14,2,7,5] chosen for the XORO32 instruction does well.
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-07 00:49
    evanh wrote: »
    Next report for Tony - There's two versions of the numbers in the zdist_report, I think the first one is the correct one but that's not how the pseudo-code was written. The second one is as per the pseudo-code.

    Evan, a small correction is are needed in your C code from
    	// read pair array and increment freq values
    	for( irng = 0; irng < (1UL<<32)-1; irng++ )
    

    to
    	// read pair array and increment freq values
    	for( irng = 0; irng < (1UL<<32); irng++ )
    

    so that all 2^32 pairs are read. However, I doubt there is much need for further distribution tests.

    Looking at the zero run frequency distributions or zfreq for short, I'm not convinced that zfreq(0) is calculated correctly. Having said that, zfreq(n)/zfreq(n+1) ~ 2.71828 = e for most values of n, including n = 0. In other words, the zero run distribution is an exponential decay function.
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-07 12:25
    evanh wrote: »
    Ouch, Melisa isn't impressed. :(

    But Seba is unfazed.
    evanh wrote: »
    I'm not convince her concerns are entirely valid for what we are wanting though:
    1: The progressiveness in state changes are hidden by the scrambler. That's the scrambler's job.
    2: Algorithmically predictable is a given. Not a concern to us. This isn't for cryptography.
    3: Invertible I don't understand. She seems focused on particular multipliers there. Maybe it's similar to predictability in that it can be hacked. I'm unsure how important this is, but it just sounds like it needs new constants. No shortage of those to choose from.

    The paper explains the theoretical basis for the multipliers in the * and ** scramblers.

    I'm wondering how often people will multiply millions of outputs by the same value of 57.

  • evanhevanh Posts: 15,091
    edited 2018-05-07 02:13
    TonyB_ wrote: »
    Evan, a small correction is are needed in your C code from ...

    It'd need written, in the prior loop, first.
    I think it's correct already though. With the initial call to next_xoro(), there is a total of 2^32 random numbers generated. This should correctly count the wraparound pair.

    Doh! I see now. I wasn't really trying to understand the code. The first loop is effectively building indexes into the array - which can be any 32-bit index.



  • evanh wrote: »
    TonyB_ wrote: »
    Evan, a small correction is are needed in your C code from ...

    It'd need written, in the prior loop, first.
    I think it's correct already though. With the initial call to next_xoro(), there is a total of 2^32 random numbers generated. This should correctly count the wraparound pair.

    next_xoro() loop is correct as period is 2^32-1 and an initial iteration is needed to get the first "half pair" but the loop that increments freq values is definitely one short as 2^32 pairs must be read.
  • evanhevanh Posts: 15,091
    edited 2018-05-07 02:35
    That's interesting, looks like this is where C's do-while loop comes into its own. The other loop constructs, for() and while(), don't allow all values of an integer to be used because there is an implicit loop completion test at both ends of the loop.

    Pity the do-while doesn't ascetically conform to common source formatting styles. That's probably the main reason I don't normally use it.

  • evanhevanh Posts: 15,091
    I've coded the generalised smaller than 8-bit sampling aperture now, and run the 1-bit sampling on the our select candidates. Everything went as expected until I hit [ 6 2 3 9]. It strangely has one seriously bad score at position 13 and there is no sign of this at 8-bit sampling. :(
    __________________________________________________________________________________________________________
    
      Xoroshiro32(16)++ PractRand Score Table.  Build 2018-05-08 12:48:22 +1200
        PractRand v0.93 options: stdin -multithreaded -te 1 -tf 2 -tlmin 1KB
        Scoring ran from 2018-05-08 12:30:20 to 2018-05-08 12:34:02.  Double Full Period = 16 GB
    __________________________________________________________________________________________________________
                    Sampling apertures of the generator output, labelled as most to least bit-significance
      Candidate    ----------------------------------------------------------------------------------------
    [ A  B  C  D]  15:00 14:00 13:00 15:01 15:02  6:15  5:14  4:13  3:12  2:11  1:10  0:09 15:08 14:07 13:06 12:05 11:04 10:03  9:02  8:01  7:00 15:15 14:14 13:13 12:12 11:11 10:10  9:09  8:08  7:07  6:06  5:05  4:04  3:03  2:02  1:01  0:00
    ==========================================================================================================
    [ 5  2  6  9]     1G    4G    2G    2G    1G  512M    1G    2G    1G  256M  256M    1G    2G    2G    1G    1G    1G    2G    1G    1G    1G    1G    1G  512M    1G  512M    1G    1G    1G    1G  512M    1G    1G    1G    1G    1G    1G
    [ 6  2  5  5]   512M    4G    4G    4G    2G    1G    1G  512M  512M    1G    1G    1G    1G    1G    1G  512M    1G    1G  512M    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G
    [ 6  2  5  9]     1G    4G    2G    4G    1G    1G    2G    2G    2G  512M  256M  512M    2G    1G  256M    1G    1G    1G    1G    1G    2G    1G    1G    1G    1G    1G    1G  256M    1G    1G    1G    1G    1G    1G    1G    1G    1G
    [14  2  7  5]   256M    4G    4G    2G    4G    1G    1G    1G    1G  512M  256M    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G
    [14  2  7  6]   512M    8G    2G    4G    2G  512M    1G    2G    1G    1G    1G    1G    2G    1G  256M  256M    2G  512M  512M  512M  512M    1G    1G    1G    1G    1G    1G    1G    1G    1G  512M    1G    1G    1G    1G    1G    1G
    [13  5 10 10]     1G    8G    4G    8G    2G  512M  512M  512M  512M  512M  512M  512M  512M    1G  512M  512M    1G    1G    1G  512M  512M    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G
    [ 3  2  6  5]   512M    4G    2G    2G    2G    1G    1G    1G    1G    1G    1G    1G    1G  512M  512M  512M  512M    1G    1G    1G    1G    1G    1G  256M    1G    1G    1G    1G    1G    1G  512M    1G    1G    1G    1G    1G    1G
    [ 6  2  3  9]   512M    4G    2G    4G    2G    2G    2G    1G    2G    1G    1G    1G    1G    1G    1G    1G    1G  512M    1G    1G    1G    1G    1G    2M    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G  512M
    [ 6  2 11  6]   512M    4G    2G    8G    2G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    2G    1G    1G    2G  512M    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G
    

    Looking at that particular Practrand report file, it hasn't gone far over the threshold. In fact I'm a little surprised by how narrow that one seems to be. I've force a rerun with no termination and it went right to the expected 1 GB without further fails. So I'll put that down to PractRand being a little too sensitive on a particular test.
    BEGIN  ... at 2018-05-08 13:15:26
    
    PractRand scoring candidate [6 2 3 9] of Xoroshiro32(16)++ random generator.
    Without parity replacement bit.
    PractRand v0.93 options: stdin -multithreaded -te 1 -tf 2 -tlmin 1KB -tlmaxonly
    
    Sampling width 1, position 13
    
    RNG_test using PractRand version 0.93
    RNG = RNG_stdin, seed = 0x9d8a22e4
    test set = expanded, folding = extra
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 1 kilobyte (2^10 bytes), time= 0.4 seconds
      no anomalies in 14 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 2 kilobytes (2^11 bytes), time= 0.7 seconds
      no anomalies in 19 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 4 kilobytes (2^12 bytes), time= 1.0 seconds
      no anomalies in 56 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 8 kilobytes (2^13 bytes), time= 1.7 seconds
      Test Name                         Raw       Processed     Evaluation
      [Low4/16]BCFN_FF(2+0):freq        R=  +7.1  p~=   5e-6    mildly suspicious
      ...and 113 test result(s) without anomalies
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 16 kilobytes (2^14 bytes), time= 2.9 seconds
      no anomalies in 179 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 32 kilobytes (2^15 bytes), time= 4.5 seconds
      no anomalies in 246 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 64 kilobytes (2^16 bytes), time= 6.4 seconds
      no anomalies in 316 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 128 kilobytes (2^17 bytes), time= 8.7 seconds
      no anomalies in 367 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 256 kilobytes (2^18 bytes), time= 10.9 seconds
      Test Name                         Raw       Processed     Evaluation
      [Low1/32]BCFN_FF(2+2):freq        R=  +6.6  p~=   2e-5    unusual          
      ...and 421 test result(s) without anomalies
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 512 kilobytes (2^19 bytes), time= 13.3 seconds
      no anomalies in 476 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 1 megabyte (2^20 bytes), time= 15.7 seconds
      no anomalies in 531 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 2 megabytes (2^21 bytes), time= 18.2 seconds
      Test Name                         Raw       Processed     Evaluation
      [Low1/8]FPF-14+6/4:cross          R=  +5.1  p =  2.3e-4   unusual          
      [Low1/16]BCFN_FF(2+8):freq        R= +12.4  p~=   5e-15     FAIL           
      [Low1/32]BCFN_FF(2+7):freq        R=  +9.1  p~=   5e-9    suspicious       
      ...and 582 test result(s) without anomalies
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 4 megabytes (2^22 bytes), time= 20.8 seconds
      Test Name                         Raw       Processed     Evaluation
      [Low1/16]DC6-9x1Bytes-1           R=  +7.4  p =  4.3e-4   unusual          
      [Low1/32]BCFN_FF(2+8):freq        R=  +8.0  p~=   2e-7    unusual          
      ...and 639 test result(s) without anomalies
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 8 megabytes (2^23 bytes), time= 23.6 seconds
      Test Name                         Raw       Processed     Evaluation
      [Low8/32]BCFN_FF(2+0):freq        R=  +6.6  p~=   1e-5    unusual          
      ...and 693 test result(s) without anomalies
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 16 megabytes (2^24 bytes), time= 26.9 seconds
      no anomalies in 747 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 32 megabytes (2^25 bytes), time= 30.5 seconds
      no anomalies in 796 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 64 megabytes (2^26 bytes), time= 34.6 seconds
      no anomalies in 843 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 128 megabytes (2^27 bytes), time= 39.4 seconds
      no anomalies in 891 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 256 megabytes (2^28 bytes), time= 45.6 seconds
      no anomalies in 938 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 512 megabytes (2^29 bytes), time= 53.5 seconds
      no anomalies in 985 test result(s)
    
    rng=RNG_stdin, seed=0x9d8a22e4
    length= 1 gigabyte (2^30 bytes), time= 66.3 seconds
      Test Name                         Raw       Processed     Evaluation
      BCFN_FF(2+0,13-1,T)               R= +26.5  p =  1.0e-13    FAIL           
      BCFN_FF(2+1,13-1,T)               R= +31.1  p =  3.4e-16    FAIL !         
      BCFN_FF(2+2,13-1,T)               R= +35.8  p =  9.7e-19    FAIL !         
      BCFN_FF(2+3,13-1,T)               R= +43.1  p =  1.1e-22    FAIL !!        
      BCFN_FF(2+4,13-2,T)               R= +26.8  p =  2.6e-13    FAIL           
      BCFN_FF(2+5,13-3,T)               R= +26.1  p =  3.9e-12   VERY SUSPICIOUS 
      BCFN_FF(2+6,13-3,T)               R= +26.1  p =  3.9e-12   VERY SUSPICIOUS 
      BCFN_FF(2+7,13-4,T)               R= +17.5  p =  1.3e-7   suspicious       
      BCFN_FF(2+6):freq                 R=  +8.3  p~=   1e-7    mildly suspicious
      BCFN_FF(2+7):freq                 R=  +8.1  p~=   2e-7    unusual          
      BCFN_FF(2+8):freq                 R= +11.5  p~=   3e-13    VERY SUSPICIOUS 
      BCFN_FF(2+9):freq                 R= +12.1  p~=   1e-14     FAIL           
      DC6-9x1Bytes-1                    R= +20.9  p =  5.4e-11    FAIL           
      DC6-6x2Bytes-1                    R= +37.5  p =  6.8e-18    FAIL !         
      DC6-5x4Bytes-1                    R= +57.3  p =  4.0e-35    FAIL !!!       
      Gap-16:A                          R= +67.3  p =  1.1e-58    FAIL !!!!      
      Gap-16:B                          R= +47.1  p =  3.3e-40    FAIL !!!       
      [Low4/16]Gap-16:A                 R=  +5.5  p =  3.8e-4   unusual          
      [Low4/32]Gap-16:A                 R=  +6.2  p =  9.5e-5   unusual          
      [Low8/32]BCFN_FF(2+1,13-2,T)      R= +11.0  p =  3.1e-5   mildly suspicious
      [Low8/32]DC6-9x1Bytes-1           R= +19.7  p =  2.3e-10   VERY SUSPICIOUS 
      [Low8/32]DC6-6x2Bytes-1           R=  +9.6  p =  5.4e-5   mildly suspicious
      [Low8/32]Gap-16:A                 R= +26.0  p =  1.8e-20    FAIL !!        
      [Low8/32]Gap-16:B                 R= +15.0  p =  3.4e-12    FAIL           
      [Low8/64]BCFN_FF(2+0,13-3,T)      R=  +9.6  p =  2.4e-4   unusual          
      [Low8/64]DC6-9x1Bytes-1           R= +19.5  p =  1.4e-11    FAIL           
      [Low8/64]DC6-6x2Bytes-1           R= +11.0  p =  2.7e-6   suspicious       
      [Low8/64]Gap-16:A                 R= +23.5  p =  1.6e-19    FAIL !         
      [Low8/64]Gap-16:B                 R= +10.1  p =  4.2e-8   very suspicious  
      ...and 1010 test result(s) without anomalies
    
  • evanhevanh Posts: 15,091
    edited 2018-05-08 01:44
    The above exercise is me thinking that 8-bit sampling at each bit position is a good way to check each bit position of the generator's output.

    I'm happy to say that not only is 8-bit sampling a good way to do it, but the best way. Practrand internally works on bytes and bigger. But it is stated in the documentation that it is also most sensitive to the patterns in bit0 of the incoming bytes. This means that by shifting an 8-bit sampling window, on a per run basis, to align Practrand's bit0 to each bit of the generator we can test each output bit one by one.

  • evanhevanh Posts: 15,091
    edited 2018-05-08 01:49
    BTW: I can now sample the generator output at any width from 1-bit up to the width of the generator itself. And the generator can be anything from 8-bit to 64-bit. With 64-bit being a Xoroshrio128.

  • evanhevanh Posts: 15,091
    edited 2018-05-08 04:17
    Here's a solid confirmation of how useless the 1-bit apertures are. I've chosen a normally poor scoring candidate, [ 4 7 15 11], and run all sampling cases on it. The 1-bit apertures didn't show anything unusual when they clearly should have:
    [ A  B  C  D]  15:00 14:00 13:00 15:01 15:02  6:15  5:14  4:13  3:12  2:11  1:10  0:09 15:08 14:07 13:06 12:05 11:04 10:03  9:02  8:01  7:00 15:15 14:14 13:13 12:12 11:11 10:10  9:09  8:08  7:07  6:06  5:05  4:04  3:03  2:02  1:01  0:00
    ==========================================================================================================
    [ 4  7 15 11]     4M  128M   64M  512M  256M    8M    4M    4M    4M    4M    8M    1G  512M  512M  512M    1G    1G    1G    1G   64M    4M    1G    1G    1G  512M    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G
    
  • evanh wrote: »
    The above exercise is me thinking that 8-bit sampling at each bit position is a good way to check each bit position of the generator's output.

    I'm happy to say that not only is 8-bit sampling a good way to do it, but the best way. Practrand internally works on bytes and bigger. But it is stated in the documentation that it is also most sensitive to the patterns in bit0 of the incoming bytes. This means that by shifting an 8-bit sampling window, on a per run basis, to align Practrand's bit0 to each bit of the generator we can test each output bit one by one.

    Each bit can be tested as the lsb of a byte but the other seven bits are also being tested.
    evanh wrote: »
    BTW: I can now sample the generator output at any width from 1-bit up to the width of the generator itself. And the generator can be anything from 8-bit to 64-bit. With 64-bit being a Xoroshiro128.

    Excellent!
    evanh wrote: »
    Here's a solid confirmation of how useless the 1-bit apertures are. I've chosen a normally poor scoring candidate, [ 4 7 15 11], and run all sampling cases on it. The 1-bit apertures didn't show anything unusual when they clearly should have:
    [ A  B  C  D]  15:00 14:00 13:00 15:01 15:02  6:15  5:14  4:13  3:12  2:11  1:10  0:09 15:08 14:07 13:06 12:05 11:04 10:03  9:02  8:01  7:00 15:15 14:14 13:13 12:12 11:11 10:10  9:09  8:08  7:07  6:06  5:05  4:04  3:03  2:02  1:01  0:00
    ==========================================================================================================
    [ 4  7 15 11]     4M  128M   64M  512M  256M    8M    4M    4M    4M    4M    8M    1G  512M  512M  512M    1G    1G    1G    1G   64M    4M    1G    1G    1G  512M    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G
    

    Thanks Evan, it was worthwhile testing.

    According to your byte theory, 4-bit samples should have better scores than 8-bit samples.

Sign In or Register to comment.