Random/LFSR on P2

1404143454675

Comments

  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-07 - 02:32:59
    As an independent check, because I can't use PractRand for various reasons, I thought of a simple test: how often an output is repeated, i.e. two successive outputs the same. For xoroshiro32 with 32-bit state and 16-bit output from 0-65535, the probability of a repeat is 1/65536 and the expected total number of repeats is (2^32-1)/65536 = 65536.

    It would be most unrandom if every output repeated exactly once, some will repeat twice or more and others never. If the output is truly random there should be a binomial distribution of repeats, with relative frequencies as follows:
    0 repeats = 1/0! = 1
    1 repeat  = 1/1! = 1
    2 repeats = 1/2! = 1/2
    3 repeats = 1/3! = 1/6
    4 repeats = 1/4! = 1/24
    5 repeats = 1/5! = 1/120
    6 repeats = 1/6! = 1/720
    7 repeats = 1/7! = 1/5040
    8 repeats = 1/8! = 1/40320
    etc.
    

    The sum of 1/0!+1/1!+1/2!+1/3!+1/4!... is the number e = 2.71828...

    If the repeat total = 65536, the expected distribution with values to the nearest integer is:
    0 repeats = 24109
    1 repeat  = 24109
    2 repeats = 12055
    3 repeats = 4018
    4 repeats = 1005
    5 repeats = 201
    6 repeats = 33
    7 repeats = 5
    8 repeats = 1
    9 repeats = 0
    

    The repeat frequency test was intended to help eliminate the worst, not select the best. Some test results to follow ...
    Formerly known as TonyB
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-07 - 01:49:34
    Repeat frequencies for xoroshiro[16]32++ [5,2,6,d]
    Actual values
    # a,  b,  c,  d, repeats,    f0,    f1,    f2,    f3,    f4,    f5,    f6,    f7,    f8,    f9,   f10,   f11
      5,  2,  6,  0,   65109, 30464, 14759, 14055,  3611,  2085,   361,   161,    28,     9,     2,     1,     0
      5,  2,  6,  1,   65292, 24077, 24164, 12198,  3907,   989,   157,    38,     6,     0,     0,     0,     0
      5,  2,  6,  2,   65600, 23935, 24408, 11888,  4093,   982,   183,    37,     9,     0,     1,     0,     0
      5,  2,  6,  3,   66373, 23906, 23967, 12198,  4145,  1067,   215,    34,     4,     0,     0,     0,     0
      5,  2,  6,  4,   65403, 24228, 23982, 12130,  3911,  1051,   183,    48,     3,     0,     0,     0,     0
      5,  2,  6,  5,   65771, 24023, 24102, 12107,  4039,  1031,   196,    33,     4,     1,     0,     0,     0
      5,  2,  6,  6,   65561, 23961, 24351, 12030,  3913,  1049,   187,    35,    10,     0,     0,     0,     0
      5,  2,  6,  7,   66121, 23824, 24240, 12083,  4110,  1047,   199,    30,     2,     1,     0,     0,     0
      5,  2,  6,  8,   65662, 25494, 22766, 11376,  4126,  1258,   394,    94,    26,     0,     2,     0,     0
      5,  2,  6,  9,   66271, 23748, 24207, 12199,  4132,  1009,   216,    21,     4,     0,     0,     0,     0
      5,  2,  6, 10,   65744, 24084, 24022, 12107,  4069,  1031,   171,    43,     8,     1,     0,     0,     0
      5,  2,  6, 11,   65929, 25264, 22861, 11461,  4220,  1298,   329,    77,    21,     5,     0,     0,     0
      5,  2,  6, 12,   65861, 23932, 24241, 12090,  3968,  1039,   226,    31,     8,     1,     0,     0,     0
      5,  2,  6, 13,   65259, 24347, 24014, 11892,  3993,  1025,   217,    39,     9,     0,     0,     0,     0
      5,  2,  6, 14,   65262, 24109, 24206, 12082,  3934,   971,   204,    25,     4,     1,     0,     0,     0
      5,  2,  6, 15,   65517, 23548, 24712, 12291,  3908,   909,   148,    17,     3,     0,     0,     0,     0
    #binomial, , , ,   65536, 24109, 24109, 12055,  4018,  1005,   201,    33,     5,     1,     0,     0,     0
    

    Repeat frequencies for xoroshiro[16]32++ [5,2,6,d]
    Actual-Expected values
    # a,  b,  c,  d, repeats,    f0,    f1,    f2,    f3,    f4,    f5,    f6,    f7,    f8,    f9,   f10,   f11
      5,  2,  6,  0,    -427,  6355, -9350,  2000,  -407,  1080,   160,   128,    23,     8,     2,     1,     0
      5,  2,  6,  1,    -244,   -32,    55,   143,  -111,   -16,   -44,     5,     1,    -1,     0,     0,     0
      5,  2,  6,  2,      64,  -174,   299,  -167,    75,   -23,   -18,     4,     4,    -1,     1,     0,     0
      5,  2,  6,  3,     837,  -203,  -142,   143,   127,    62,    14,     1,    -1,    -1,     0,     0,     0
      5,  2,  6,  4,    -133,   119,  -127,    75,  -107,    46,   -18,    15,    -2,    -1,     0,     0,     0
      5,  2,  6,  5,     235,   -86,    -7,    52,    21,    26,    -5,     0,    -1,     0,     0,     0,     0
      5,  2,  6,  6,      25,  -148,   242,   -25,  -105,    44,   -14,     2,     5,    -1,     0,     0,     0
      5,  2,  6,  7,     585,  -285,   131,    28,    92,    42,    -2,    -3,    -3,     0,     0,     0,     0
      5,  2,  6,  8,     126,  1385, -1343,  -679,   108,   253,   193,    61,    21,    -1,     2,     0,     0
      5,  2,  6,  9,     735,  -361,    98,   144,   114,     4,    15,   -12,    -1,    -1,     0,     0,     0
      5,  2,  6, 10,     208,   -25,   -87,    52,    51,    26,   -30,    10,     3,     0,     0,     0,     0
      5,  2,  6, 11,     393,  1155, -1248,  -594,   202,   293,   128,    44,    16,     4,     0,     0,     0
      5,  2,  6, 12,     325,  -177,   132,    35,   -50,    34,    25,    -2,     3,     0,     0,     0,     0
      5,  2,  6, 13,    -277,   238,   -95,  -163,   -25,    20,    16,     6,     4,    -1,     0,     0,     0
      5,  2,  6, 14,    -274,     0,    97,    27,   -84,   -34,     3,    -8,    -1,     0,     0,     0,     0
      5,  2,  6, 15,     -19,  -561,   603,   236,  -110,   -96,   -53,   -16,    -2,    -1,     0,     0,     0
    #binomial, , , ,   65536, 24109, 24109, 12055,  4018,  1005,   201,    33,     5,     1,     0,     0,     0
    

    Repeat frequencies for xoroshiro[16]32++ [14,2,7,d]
    Actual values
    # a,  b,  c,  d, repeats,    f0,    f1,    f2,    f3,    f4,    f5,    f6,    f7,    f8,    f9,   f10,   f11
     14,  2,  7,  0,   65526, 24159, 24092, 11990,  4021,  1023,   212,    34,     5,     0,     0,     0,     0
     14,  2,  7,  1,   65641, 23948, 24286, 12032,  4045,  1012,   175,    34,     3,     1,     0,     0,     0
     14,  2,  7,  2,   65586, 23817, 24444, 12123,  3985,   936,   193,    34,     4,     0,     0,     0,     0
     14,  2,  7,  3,   65441, 24113, 24115, 12097,  3985,   992,   201,    30,     2,     0,     0,     1,     0
     14,  2,  7,  4,   65502, 24069, 24233, 11980,  3999,  1014,   201,    31,     7,     2,     0,     0,     0
     14,  2,  7,  5,   65337, 24191, 24024, 12146,  3940,  1021,   174,    33,     7,     0,     0,     0,     0
     14,  2,  7,  6,   65705, 24174, 24017, 12004,  4014,  1053,   227,    38,     9,     0,     0,     0,     0
     14,  2,  7,  7,   65944, 23775, 24285, 12253,  4013,   982,   187,    36,     5,     0,     0,     0,     0
     14,  2,  7,  8,   65430, 26025, 22216, 11183,  4265,  1350,   371,    91,    29,     5,     1,     0,     0
     14,  2,  7,  9,   65835, 23816, 24285, 12197,  4034,   997,   177,    29,     1,     0,     0,     0,     0
     14,  2,  7, 10,   65636, 23988, 24194, 12141,  3968,  1010,   200,    30,     4,     1,     0,     0,     0
     14,  2,  7, 11,   65596, 24102, 24150, 11968,  4048,  1014,   218,    32,     4,     0,     0,     0,     0
     14,  2,  7, 12,   65563, 24154, 23987, 12129,  4022,  1006,   206,    27,     4,     1,     0,     0,     0
     14,  2,  7, 13,   65817, 23964, 24202, 12039,  4081,   995,   221,    29,     5,     0,     0,     0,     0
     14,  2,  7, 14,   65251, 24307, 23986, 12040,  3930,  1012,   222,    36,     3,     0,     0,     0,     0
     14,  2,  7, 15,   65440, 24132, 24109, 12049,  4031,   991,   178,    37,     8,     1,     0,     0,     0
    #binomial, , , ,   65536, 24109, 24109, 12055,  4018,  1005,   201,    33,     5,     1,     0,     0,     0
    

    Repeat frequencies for xoroshiro[16]32++ [14,2,7,d]
    Actual-Expected values
    # a,  b,  c,  d, repeats,    f0,    f1,    f2,    f3,    f4,    f5,    f6,    f7,    f8,    f9,   f10,   f11
     14,  2,  7,  0,     -10,    50,   -17,   -65,     3,    18,    11,     1,     0,    -1,     0,     0,     0
     14,  2,  7,  1,     105,  -161,   177,   -23,    27,     7,   -26,     1,    -2,     0,     0,     0,     0
     14,  2,  7,  2,      50,  -292,   335,    68,   -33,   -69,    -8,     1,    -1,    -1,     0,     0,     0
     14,  2,  7,  3,     -95,     4,     6,    42,   -33,   -13,     0,    -3,    -3,    -1,     0,     1,     0
     14,  2,  7,  4,     -34,   -40,   124,   -75,   -19,     9,     0,    -2,     2,     1,     0,     0,     0
     14,  2,  7,  5,    -199,    82,   -85,    91,   -78,    16,   -27,     0,     2,    -1,     0,     0,     0
     14,  2,  7,  6,     169,    65,   -92,   -51,    -4,    48,    26,     5,     4,    -1,     0,     0,     0
     14,  2,  7,  7,     408,  -334,   176,   198,    -5,   -23,   -14,     3,     0,    -1,     0,     0,     0
     14,  2,  7,  8,    -106,  1916, -1893,  -872,   247,   345,   170,    58,    24,     4,     1,     0,     0
     14,  2,  7,  9,     299,  -293,   176,   142,    16,    -8,   -24,    -4,    -4,    -1,     0,     0,     0
     14,  2,  7, 10,     100,  -121,    85,    86,   -50,     5,    -1,    -3,    -1,     0,     0,     0,     0
     14,  2,  7, 11,      60,    -7,    41,   -87,    30,     9,    17,    -1,    -1,    -1,     0,     0,     0
     14,  2,  7, 12,      27,    45,  -122,    74,     4,     1,     5,    -6,    -1,     0,     0,     0,     0
     14,  2,  7, 13,     281,  -145,    93,   -16,    63,   -10,    20,    -4,     0,    -1,     0,     0,     0
     14,  2,  7, 14,    -285,   198,  -123,   -15,   -88,     7,    21,     3,    -2,    -1,     0,     0,     0
     14,  2,  7, 15,     -96,    23,     0,    -6,    13,   -14,   -23,     4,     3,     0,     0,     0,     0
    #binomial, , , ,   65536, 24109, 24109, 12055,  4018,  1005,   201,    33,     5,     1,     0,     0,     0
    
    Formerly known as TonyB
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-07 - 02:54:57
    Edited summary:

    Repeat frequencies for xoroshiro[16]32++
    Actual-Expected values
    # a,  b,  c,  d, repeats,    f0,    f1,    f2,    f3,    f4,    f5,    f6,    f7,    f8,    f9,   f10,   f11
      5,  2,  6,  9,     735,  -361,    98,   144,   114,     4,    15,   -12,    -1,    -1,     0,     0,     0
     14,  2,  7,  5,    -199,    82,   -85,    91,   -78,    16,   -27,     0,     2,    -1,     0,     0,     0
     14,  2,  7,  6,     169,    65,   -92,   -51,    -4,    48,    26,     5,     4,    -1,     0,     0,     0
    #binomial, , , ,   65536, 24109, 24109, 12055,  4018,  1005,   201,    33,     5,     1,     0,     0,     0
    

    As can be seen, [5,2,6,9] repeat frequency is bad and yet it was the best performer in extended PractRand tests.
    [6,2,5,9] is similar to [5,2,6,9] but I didn't save it.

    0 * f0 + 1 * f1 + 2 * f2 + 3 * f3 + ... = repeats
    f0 + f1 + f2 + f3 + ... = 65536
    Formerly known as TonyB
  • Rimshot:

    Pick one at, ahem... :D
    Do not taunt Happy Fun Ball! @opengeekorg ---> Be Excellent To One Another SKYPE = acuity_doug
    Parallax colors simplified: https://forums.parallax.com/discussion/123709/commented-graphics-demo-spin<br>
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-07 - 02:58:12
    At first Seba suggested exactly half rotation for constant d, 8 in this case, but he changed his mind after running some tests. The repeat frequency confirms this, although the worst d might not be 8 if one of the other constants is 8. Worst d +/- 1 are usually not great.
    Formerly known as TonyB
  • The missing Crush and BigCrush test results are here, thanks to Seba. Please stand by ...
    Formerly known as TonyB
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-07 - 03:31:54
    xoroshiro[16]32++ [14,2,7,5] Crush
    ========= Summary results of Crush =========
    
     Version:          TestU01 1.2.3
     Generator:        xoroshiro[16]32++-14-2-7
     Number of statistics:  144
     Total CPU time:   00:29:09.44
     The following tests gave p-values outside [0.001, 0.9990]:
     (eps  means a value < 1.0e-300):
     (eps1 means a value < 1.0e-15):
    
           Test                          p-value
     ----------------------------------------------
      1  SerialOver, t = 2              1 -  5.1e-5
      2  SerialOver, t = 4               1.3e-8
     42  MaxOft, t = 10                 1 -  1.1e-6
     43  MaxOft, t = 20                 1 -  2.7e-5
     44  MaxOft, t = 30                 1 -  5.7e-9
     ----------------------------------------------
     All other tests were passed
    

    xoroshiro[16]32++ [14,2,7,6] Crush
    ========= Summary results of Crush =========
    
     Version:          TestU01 1.2.3
     Generator:        xoroshiro[16]32++-14-2-7
     Number of statistics:  144
     Total CPU time:   00:35:46.09
     The following tests gave p-values outside [0.001, 0.9990]:
     (eps  means a value < 1.0e-300):
     (eps1 means a value < 1.0e-15):
    
           Test                          p-value
     ----------------------------------------------
      1  SerialOver, t = 2              1 - eps1
     41  MaxOft, t = 5                   0.9992 
     44  MaxOft, t = 30                 1 -  9.6e-6
     ----------------------------------------------
     All other tests were passed
    

    xoroshiro[16]32++ [14,2,7,5] BigCrush
    ========= Summary results of BigCrush =========
    
     Version:          TestU01 1.2.3
     Generator:        xoroshiro[16]32++-14-2-7
     Number of statistics:  160
     Total CPU time:   03:12:04.36
     The following tests gave p-values outside [0.001, 0.9990]:
     (eps  means a value < 1.0e-300):
     (eps1 means a value < 1.0e-15):
    
           Test                          p-value
     ----------------------------------------------
      2  SerialOver, r = 22              1.1e-4
     34  Gap, r = 0                       eps  
     35  Gap, r = 25                      eps  
     36  Gap, r = 0                       eps  
     37  Gap, r = 20                      eps  
     46  MaxOft, t = 8                  1 - eps1
     47  MaxOft, t = 16                 1 - eps1
     48  MaxOft, t = 24                 1 - eps1
     49  MaxOft, t = 32                 1 - eps1
     65  SumCollector                    8.3e-4
     ----------------------------------------------
     All other tests were passed
    

    xoroshiro[16]32++ [14,2,7,6] BigCrush
    ========= Summary results of BigCrush =========
    
     Version:          TestU01 1.2.3
     Generator:        xoroshiro[16]32++-14-2-7
     Number of statistics:  160
     Total CPU time:   03:14:37.20
     The following tests gave p-values outside [0.001, 0.9990]:
     (eps  means a value < 1.0e-300):
     (eps1 means a value < 1.0e-15):
    
           Test                          p-value
     ----------------------------------------------
      1  SerialOver, r = 0                eps  
      2  SerialOver, r = 22             1 -  1.7e-5
     34  Gap, r = 0                     9.1e-11
     35  Gap, r = 25                      eps  
     36  Gap, r = 0                       eps  
     37  Gap, r = 20                      eps  
     46  MaxOft, t = 8                  1 - 4.6e-15
     47  MaxOft, t = 16                 1 - eps1
     48  MaxOft, t = 24                 1 - eps1
     49  MaxOft, t = 32                 1 - eps1
     65  SumCollector                    7.4e-4
     ----------------------------------------------
     All other tests were passed
    

    Tests failed:
    		Crush	BigCrush
    [14,2,7,5]	  5	   10
    [14,2,7,6]	  3	   11
    

    Conclusion:
    I think we can leave XORO32 as it is.
    Formerly known as TonyB
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-07 - 03:22:36
    BigCrush trumps Crush?
    Formerly known as TonyB
  • cgraceycgracey Posts: 11,064
    edited 2018-04-07 - 03:16:53
    I forget. Do we have the [14,2,7,6] or [14,2,7,5] now?
  • We switched from [14,2,7,6] to [14,2,7,5] on 8th March.
    Formerly known as TonyB
  • They're all good. The other three are looking attractive too. I have no strong argument in any one direction.

    "There's no huge amount of massive material
    hidden in the rings that we can't see,
    the rings are almost pure ice."
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-07 - 21:28:36
    I've told Seba the P2 design is finished and the first chip will have 1 * xoroshiro128 + 8 * xoroshiro32++ [14,2,7,5] so we can't change it now! :)

    Seba has helped us a lot via email and I've thanked him and David for that and their xoroshiro algorithms, on behalf of all of us.
    [Sebastiano Vigna & David Blackman.]

    * * * * * * * * * *

    Chip,

    Seba would like to mention in his forthcoming paper that the new xoroshiro128 algorithm is/will be in a processor. He asked me how to quote Parallax and the P2 correctly.
    Formerly known as TonyB
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-07 - 21:56:46
    evanh wrote: »
      Xoroshiro32(16)++ PractRand Score Table.  PractRand v0.93 options: -multithreaded -te 1 -tf 2 -tlmin 1KB
    __________________________________________________________________________________________________________
                    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 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    2G    2G    1G    1G    1G    2G    1G    1G    1G
    [ 6  2  5  9]     1G    4G    2G    4G    1G    2G    1G  256M    1G    1G    1G    1G    1G    2G
    [14  2  7  5]   256M    4G    4G    2G    4G    1G    1G    1G    1G    1G    1G    1G    1G    1G
    [14  2  7  6]   512M    8G    2G    4G    2G    2G    1G  256M  256M    2G  512M  512M  512M  512M
    [15  4 12  9]   256M   16G    8G    8G    2G    1G    1G  512M  512M  512M    1G    1G    1G    1G
    
    Notably, with full extended options, [14 2 7 5] degrades to 256 MB on the full width sampling.

    The main reason for the switch to [14,2,7,5] is its consistency. All nine 8-bit samples above have the same score. Evan, is it worth trying the five 12-bit groups? Also, is your new xoroshiro128 test still running?

    Formerly known as TonyB
  • Same comment here, is a license needed to insure no long term entanglements?

    Do not taunt Happy Fun Ball! @opengeekorg ---> Be Excellent To One Another SKYPE = acuity_doug
    Parallax colors simplified: https://forums.parallax.com/discussion/123709/commented-graphics-demo-spin<br>
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-07 - 22:55:03
    Parallax has had permission to use xoroshiro++ without any strings attached since last November. I've just asked Seba to confirm the same applies to the new xoroshiro128.
    Formerly known as TonyB
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-08 - 01:12:17
    Question asked and answered today:
    TonyB_ wrote:
    Please confirm that Parallax Inc. can use xoroshiro128 freely and without any strings attached, as for xoroshiro++.
    Yes, totally, they are in the public domain (soon).

    Chip, is the above good enough for you? Something very similar was for xoroshiro++.
    Formerly known as TonyB
  • The only formal declaration I've found is in the older Xorshift source code:
    /* Written in 2014-2016 by Sebastiano Vigna (vigna@acm.org)

    To the extent possible under law, the author has dedicated all copyright
    and related and neighboring rights to this software to the public domain
    worldwide. This software is distributed without any warranty.

    See <http://creativecommons.org/publicdomain/zero/1.0/>. */

    Tony,
    Does Seba have a handle on why we have stuck with Xoroshiro?

    Reading Melisa's blog, it is very clear that multipliers, using a full-width constant, feature highly in the high quality PRNG algorithms. A full blown multiplier is way beyond what we can handle so making do with adders is doing well to get good quality.

    Chris did indicate there is better using just adders and gave an example. But it needed a bigger adder circuit than what XORO32 was using. Chris may have been able to refine it more, dunno. In hindsight we didn't pursue that option as much as we probably should have.

    The good news is we have gone most of the way by upgrading XORO32 to the dual 16-bit adders arrangement. This is still a decent logic saving over having a single 32-bit adder.

    The free-running GETRND has also newly got a similar update to dual 64-bit adders. It now has a two stage internal circuit, ie: The random data results are always one clock lagging the state store register.

    "There's no huge amount of massive material
    hidden in the rings that we can't see,
    the rings are almost pure ice."
  • evanhevanh Posts: 6,992
    edited 2018-04-08 - 01:13:36
    Another factor I guess is the pack-of-cards type randomness. I think most algorithms have many holes in state space utilisation (period is nerf'd and potentially poor distribution). Xorshift/Xoroshiro have state iteration separated from "hash"ing. My take of this separation is it allows for independent tuning of the randomness while still fully utilising, or not, the state space.

    It also parallelises the algorithm!

    "There's no huge amount of massive material
    hidden in the rings that we can't see,
    the rings are almost pure ice."
  • evanhevanh Posts: 6,992
    edited 2018-04-08 - 01:56:45
    TonyB_ wrote: »
    ... Evan, is it worth trying the five 12-bit groups? Also, is your new xoroshiro128 test still running?
    Currently three 128's running. Two are 32-bit sampling of original algorithm while the third is 8-bit, [7:0], sampling of the Prop2's algorithm.

    They share the CPU cores a little. Max's out at about 5.3 hardware threads (virtual cores) used per running test case. Doesn't push much above 13 threads all combined though.

    As for further XORO32 testing, recent piecemeal testing has been achieved with newly added scripts that can semi-automate the testing for smaller test sets. I used one yesterday to make the partial score tables with. These new scripts don't do the CPU load checking, so I have to be careful not to fire off too many test cases at once ...

    "There's no huge amount of massive material
    hidden in the rings that we can't see,
    the rings are almost pure ice."
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-08 - 03:29:13
    evanh wrote: »
    Tony,
    Does Seba have a handle on why we have stuck with Xoroshiro?

    Reading Melisa's blog, it is very clear that multipliers, using a full-width constant, feature highly in the high quality PRNG algorithms. A full blown multiplier is way beyond what we can handle so making do with adders is doing well to get good quality.

    Chris did indicate there is better using just adders and gave an example. But it needed a bigger adder circuit than what XORO32 was using. Chris may have been able to refine it more, dunno. In hindsight we didn't pursue that option as much as we probably should have.

    The good news is we have gone most of the way by upgrading XORO32 to the dual 16-bit adders arrangement. This is still a decent logic saving over having a single 32-bit adder.

    The free-running GETRND has also newly got a similar update to dual 64-bit adders. It now has a two stage internal circuit, ie: The random data results are always one clock lagging the state store register.

    I think Seba is really pleased his and David's algorithms will be implemented in a microprocessor. Aren't you glad we've stuck with xoroshiro, after doing thousands of tests on it? It's far too late to change now, anyway, we're done.

    The two different xoroshiro algorithms in the P2 are state-of-the-art and yet don't need a great deal of logic. I think we've said as much as we can or should about the new xoroshiro128 until it is made public. We are lucky to know about either algorithm, to be honest. After I put a message on his forum about our version of the parity trick to improve xoroshiro+, Seba mentioned xoroshiro++ at the end of an email as he was curious to know whether there would be enough instruction time for the P2 to do it.

    There was more good fortune with the new xoroshiro128. We started using xoroshiro32++ in November and in the middle of February I enquired when the ++ algorithm would be announced. Seba replied that it never would be, as he had a better generator but 128-bit only. He didn't volunteer this earlier because he knew we were using a 32-bit xoroshiro++ and probably I hadn't told him the P2 also has a 128-bit generator. We might have found out about the new xoroshiro128 only after the P2 had been finished.
    Formerly known as TonyB
  • TonyB_ wrote: »
    ... Seba told me about xoroshiro++ after I put a message on his forum about our version of the parity trick to improve xoroshiro+, as he was curious to know whether there would enough time for the P2 to do it.
    Was he curious about time to product launch or instruction execution speed?

    What I'm trying to make clear here is it's the latter, instruction speed (and compactness), that has been a defining factor all along. For a hardware solution, it's hard to beat Xoroshiro on the speed, simplicity and quality all combined. I figure it is worth clarifying that this is why we started with Xoroshiro and are still using it.

    Bare in mind that Melissa is being critical towards Xoroshiro128+'s fame. She has the luxury of a fast 64-bit multiplier instruction to play with, so naturally she can demonstrate higher quality solutions that run just as fast as a software Xoroshiro does. On a software solution basis she is right to point this out.

    Obviously she has not been comparing the newer Xoroshiro versions though. So, yep, I am very grateful of Seba giving us our head start.

    "There's no huge amount of massive material
    hidden in the rings that we can't see,
    the rings are almost pure ice."
  • And then there's Ahle, who was the one that started this whole investigation.
  • cgracey wrote: »
    And then there's Ahle, who was the one that started this whole investigation.
    Yes, I've certainly learnt much about PRNGs and their uses as a result of this topic. I was totally green before this.

    I presume something else he was doing must have jogged him into thinking about progress with the Prop2 and what was then only the free running generator.

    "There's no huge amount of massive material
    hidden in the rings that we can't see,
    the rings are almost pure ice."
  • TonyB_TonyB_ Posts: 1,201
    edited 2018-04-08 - 03:30:42
    evanh wrote: »
    TonyB_ wrote: »
    ... Seba told me about xoroshiro++ after I put a message on his forum about our version of the parity trick to improve xoroshiro+, as he was curious to know whether there would be enough time for the P2 to do it.
    Was he curious about time to product launch or instruction execution speed?
    Instruction time. (Original post edited.)
    evanh wrote: »
    What I'm trying to make clear here is it's the latter, instruction speed (and compactness), that has been a defining factor all along. For a hardware solution, it's hard to beat Xoroshiro on the speed, simplicity and quality all combined. I figure it is worth clarifying that this is why we started with Xoroshiro and are still using it.
    Exactly!
    evanh wrote: »
    Bear in mind that Melissa is being critical towards Xoroshiro128+'s fame. She has the luxury of a fast 64-bit multiplier instruction to play with, so naturally she can demonstrate higher quality solutions that run just as fast as a software Xoroshiro does. On a software solution basis she is right to point this out.

    Obviously she has not been comparing the newer Xoroshiro versions though. So, yep, I am very grateful of Seba giving us our head start.
    I told Melissa all about xoroshiro++ in February. The tests mentioned in her recent post took so long that I think she started them last year:
    http://www.pcg-random.org/posts/xoroshiro-fails-truncated.html

    Any further critiques of xoroshiro+ are pointless. It's very old hat.
    Formerly known as TonyB
  • evanhevanh Posts: 6,992
    edited 2018-04-08 - 03:31:09
    TonyB_ wrote: »
    Any further critiques of xoroshiro+ are pointless. It's very old hat.
    That's not a fair judgement beyond the Prop2 at this stage. And original Xoroshiro is barely two years old!

    Maybe you could say that after the new version is actually published, but even then it would still be worth comparing new and old.

    "There's no huge amount of massive material
    hidden in the rings that we can't see,
    the rings are almost pure ice."
  • evanh wrote: »
    TonyB_ wrote: »
    Any further critiques of xoroshiro+ are pointless. It's very old hat.
    That's not a fair judgement beyond the Prop2 at this stage. And original Xoroshiro is barely two years old!

    Maybe you could say that after the new version is actually published, but even then it would still be worth comparing new and old.

    Regarding the age of hats, perhaps it's the criticism that's the headwear? Seba finds it exasperating and Melissa knew there was a better xoroshiro before making her recent blog post.

    Formerly known as TonyB
  • xoroshiro+ has not been described in a paper and it will be interesting to see how much there is about it in the one due soon.
    Formerly known as TonyB
  • evanh wrote: »
    TonyB_ wrote: »
    Evan, is it worth trying the five 12-bit groups?
    ... These new scripts don't do the CPU load checking, so I have to be careful not to fire off too many test cases at once
      Xoroshiro32(16)++ PractRand Score Table.  PractRand v0.93 options: -multithreaded -te 1 -tf 2 -tlmin 1KB
    __________________________________________________________________________________________________________
                    Sampling apertures of the generator output, labelled as most to least bit-significance
      Candidate    ----------------------------------------------------------------------------------------
    [ A  B  C  D]  15:03 14:02 13:01 12:00    15:04 14:03 13:02 12:01 11:00
    ==========================================================================================================
    [ 5  2  6  9]     2G    4G    4G    4G     512M  512M  512M  512M    1G
    [ 6  2  5  9]     2G    2G    4G    2G     512M  512M  512M  512M  256M
    [14  2  7  5]     4G    4G    4G    2G     512M    1G    1G  512M  512M
    [14  2  7  6]     4G    4G    4G    4G     512M  512M  512M  512M  512M
    [15  4 12  9]     4G    8G   16G    4G       1G    1G    1G    1G    1G
    
    "There's no huge amount of massive material
    hidden in the rings that we can't see,
    the rings are almost pure ice."
  • evanhevanh Posts: 6,992
    edited 2018-04-08 - 05:05:18
    TonyB_ wrote: »
    Seba finds it exasperating and Melissa knew there was a better xoroshiro before making her recent blog post.
    I'm sure he can handle it.

    It'll be a good comparison that can be looked back on and everyone can say those niggles are solved ... until a tougher test suite is devised, that is . :)

    "There's no huge amount of massive material
    hidden in the rings that we can't see,
    the rings are almost pure ice."
  • /* Written in 2014-2016 by Sebastiano Vigna (vigna@acm.org)

    To the extent possible under law, the author has dedicated all copyright
    and related and neighboring rights to this software to the public domain
    worldwide. This software is distributed without any warranty.

    See <http://creativecommons.org/publicdomain/zero/1.0/>. */

    I'm no copyright expert but as far as I know this is problematic. In most of the world, that has bowed down to the almighty Micky Mouse, it is impossible to put your work into the public domain. Unless you are a government or have been dead for many decades.

    Copyright protection is granted automatically when one publishes a work. I never found any mechanism by which copyright law allows one to remove that protection and place the work into the public domain. Anyone ever hear of such a thing?

    As such a statement like "To the extent possible under law... this software to the public domain..." is useless. There is no extent possible under the law.

    This why everything open source is published with one of the billion open source licenses that have been dreamed up in recent years. You can't just say "public domain" you have to license it with terms that grant users the rights you want them to have.

    Also, the creative commons link given does not work. CC does say "Currently, Creative Commons does not recommend the Public Domain Mark", for the same reasons I give above. https://creativecommons.org/choose/mark/





Sign In or Register to comment.