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

Random/LFSR on P2

1444547495092

Comments

  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-16 22:54
    zfreq(x) only has a meaning when x > 0 and zfreq(0) tells us nothing new as the code makes zfreq(0) = 2^32 - pfreq(0). The average non-zero run length = e ~ 2.718 and the average zero run length = e / (e-1) ~ 1.582. The former is greater than the latter because there are more non-zero pair values than zero ones. The number of runs is the same for both by definition (to within one at worst). I think no more distribution tests are needed and I'll put a summary of the scores together soon.
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-16 21:00
    evanh wrote: »
    Here's [14 2 7 6]
    __________________________________________________________________________________________________________
      PractRand scoring of Xoroshiro32(16)++ candidate [14 2 7 6].  Double Full Period = 16 GB.
          PractRand v0.93 options:  stdin -multithreaded -te 1 -tf 2 -tlmin 1KB
          Scoring ran from 2018-05-15 22:12:42 to unknown.  Build 2018-05-15 23:44:21 +1200
        |===00====01====02====03====04====05====06====07====08====09====10====11====12====13====14====15=
     16 |  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M
     15 |    8G    4G    4G    4G    4G    4G    4G    4G    4G    4G    4G    4G    4G    8G   16G    4G
     14 |    2G    2G    2G    2G    2G    2G    1G    2G    1G    1G    2G    2G    1G    2G    4G    4G
     13 |    4G    4G    4G    4G    4G    4G    4G    4G    4G    4G    4G    4G    4G    4G    4G    8G
     12 |  512M  512M  512M  512M  512M  512M    1G    1G    1G    1G    1G  512M  512M    1G  512M  512M
     11 |    2G    2G    4G    4G    4G    2G    4G    4G    4G    4G    4G    4G  128K    4G    4G    2G
     10 |  128K    1G    2G    2G    2G    2G    2G    2G    2G    2G    2G    1G    2G    2G    2G    2G
     09 |    4G    2G    2G    4G    4G    8G    8G    8G    4G    8G    4G    8G    2G    8G    8G    4G
     08 |  512M  512M  512M  512M    2G  256M  256M    1G    2G    1G    1G    1G    1G    2G    1G  512M
     07 |    4G    2G    2G    4G    4G    4G    2G    2G    8G    8G    4G    4G    4G    4G    4G    4G
     06 |    4G    4G    1G    2G    2G    4G    2G  512M    1G    2G    2G    2G    2G    2G    2G    2G
     05 |    1G    8K    2G    4G    4G    2G    4G    4G    4G    4G    4G    4G    4G    4G    4G    4G
     04 |    1G  512M  512M    2G  512M  256M  128M    1G  512M    1G    1G    1G    1G    4G    1G  256M
     03 |    2G    4G    2G    4G    4G    4G    4G    4G    2G    4G    4G    4G    4G    4G    4G    2G
     02 |  512M    2G    2G    2G    2G    1G  128M    2G    2G    1G    2G    2G    2G    2G    2G  128M
     01 |    1G    1G    1G    1G    1G    1G  512M    1G    1G    1G    1G    1G    1G    1G    1G    1G
    

    Evan, this full table with 256 PractRand scores is excellent. Do you have similar tables for all the 11 candidates you've been looking at recently?
  • evanhevanh Posts: 15,091
    TonyB_ wrote: »
    Thanks a lot, Evan. zfreq(0) is correct now. Looking just at zfreq, [6,2,3,9] and [6,2,11,6] do very well. Not checked others.

    [6 2 11 6] comes up clean. There is three very poor scores but they all check out as borderline BCFN_FF cases. So, really only a single 256 MB and the rest are 512 MB or better.

    Here's all nine of the every-aperture score tables, and also the extended PR reports for the three borderline cases of [6 2 11 6].
  • At some point a useful subset of all this needs to be in the P2 datasheet, along with software code.

    Its very good work. Should be published and accessible.

  • evanhevanh Posts: 15,091
    PS: [6 2 3 9] has a correctly poor score of 16 MB at aperture 2+1.
    RNG_test using PractRand version 0.93
    RNG = RNG_stdin, seed = 0xf3bf6941
    test set = expanded, folding = extra
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 1 kilobyte (2^10 bytes), time= 0.4 seconds
      no anomalies in 14 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 2 kilobytes (2^11 bytes), time= 0.7 seconds
      Test Name                         Raw       Processed     Evaluation
      FPF-14+6/4:all                    R=  -6.3  p =1-4.2e-3   unusual          
      ...and 18 test result(s) without anomalies
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 4 kilobytes (2^12 bytes), time= 1.1 seconds
      no anomalies in 56 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 8 kilobytes (2^13 bytes), time= 1.7 seconds
      no anomalies in 114 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 16 kilobytes (2^14 bytes), time= 2.9 seconds
      no anomalies in 179 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 32 kilobytes (2^15 bytes), time= 4.5 seconds
      no anomalies in 246 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 64 kilobytes (2^16 bytes), time= 6.4 seconds
      no anomalies in 316 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 128 kilobytes (2^17 bytes), time= 8.7 seconds
      no anomalies in 367 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 256 kilobytes (2^18 bytes), time= 10.9 seconds
      no anomalies in 422 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 512 kilobytes (2^19 bytes), time= 13.3 seconds
      no anomalies in 476 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 1 megabyte (2^20 bytes), time= 15.6 seconds
      no anomalies in 531 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 2 megabytes (2^21 bytes), time= 18.1 seconds
      no anomalies in 585 test result(s)
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 4 megabytes (2^22 bytes), time= 20.7 seconds
      Test Name                         Raw       Processed     Evaluation
      FPF-14+6/4:(0,14-1)               R=  +9.1  p =  8.9e-8   mildly suspicious
      FPF-14+6/4:all                    R=  +6.8  p =  8.0e-6   mildly suspicious
      FPF-14+6/4:all2                   R= +12.8  p =  3.8e-6   mildly suspicious
      ...and 638 test result(s) without anomalies
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 8 megabytes (2^23 bytes), time= 23.6 seconds
      Test Name                         Raw       Processed     Evaluation
      FPF-14+6/4:(0,14-0)               R= +10.9  p =  1.2e-9   very suspicious  
      FPF-14+6/4:all                    R=  +7.2  p =  3.0e-6   mildly suspicious
      FPF-14+6/4:all2                   R= +20.8  p =  4.7e-9   very suspicious  
      ...and 691 test result(s) without anomalies
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 16 megabytes (2^24 bytes), time= 26.8 seconds
      Test Name                         Raw       Processed     Evaluation
      FPF-14+6/4:(0,14-0)               R= +21.1  p =  3.8e-19    FAIL !         
      FPF-14+6/4:all                    R= +16.1  p =  1.2e-14    FAIL           
      FPF-14+6/4:all2                   R=+101.7  p =  1.6e-38    FAIL !!!       
      ...and 744 test result(s) without anomalies
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 32 megabytes (2^25 bytes), time= 30.4 seconds
      Test Name                         Raw       Processed     Evaluation
      FPF-14+6/16:(0,14-0)              R=  +9.4  p =  2.8e-8   suspicious       
      FPF-14+6/16:all                   R=  +6.9  p =  5.6e-6   mildly suspicious
      FPF-14+6/16:all2                  R= +14.2  p =  9.5e-7   suspicious       
      FPF-14+6/4:(0,14-0)               R= +38.1  p =  6.9e-35    FAIL !!!       
      FPF-14+6/4:(1,14-0)               R= +13.9  p =  1.9e-12   VERY SUSPICIOUS 
      FPF-14+6/4:(2,14-0)               R=  +9.9  p =  8.9e-9   suspicious       
      FPF-14+6/4:all                    R= +31.6  p =  4.1e-29    FAIL !!!       
      FPF-14+6/4:all2                   R=+372.9  p =  7.6e-141   FAIL !!!!!     
      ...and 788 test result(s) without anomalies
    
    rng=RNG_stdin, seed=0xf3bf6941
    length= 64 megabytes (2^26 bytes), time= 34.3 seconds
      Test Name                         Raw       Processed     Evaluation
      FPF-14+6/32:all                   R=  +6.3  p =  2.0e-5   mildly suspicious
      FPF-14+6/16:(0,14-0)              R= +18.0  p =  2.8e-16    FAIL           
      FPF-14+6/16:(1,14-0)              R=  +8.5  p =  1.6e-7   mildly suspicious
      FPF-14+6/16:(2,14-1)              R=  +8.7  p =  1.7e-7   mildly suspicious
      FPF-14+6/16:all                   R= +19.1  p =  2.3e-17    FAIL !         
      FPF-14+6/16:all2                  R= +90.7  p =  1.5e-34    FAIL !!!       
      FPF-14+6/4:(0,14-0)               R= +71.8  p =  4.4e-66    FAIL !!!!      
      FPF-14+6/4:(1,14-0)               R= +27.1  p =  1.0e-24    FAIL !!        
      FPF-14+6/4:(2,14-0)               R= +18.3  p =  1.4e-16    FAIL           
      FPF-14+6/4:(3,14-0)               R=  +7.8  p =  7.1e-7   mildly suspicious
      FPF-14+6/4:all                    R= +57.5  p =  1.9e-53    FAIL !!!!      
      FPF-14+6/4:all2                   R= +1383  p =  4.8e-541   FAIL !!!!!!!   
      ...and 831 test result(s) without anomalies
    
  • evanhevanh Posts: 15,091
    BTW: I currently have over 6300 report files from Practrand sloshing around the s16 testing directory. I might try to break that up a little ...

  • evanhevanh Posts: 15,091
    potatohead wrote: »
    At some point a useful subset of all this needs to be in the P2 datasheet, along with software code.
    I dunno about putting it in official Prop2 docs but here's the summary topic - https://forums.parallax.com/discussion/168188/xoroshiro-random-number-generator

    I haven't posted the sources in that topic. The testing source code is still evolving in some ways. And Tony has some of his own.

    There is a number of archives in various posts of this topic though.

  • TonyB_ wrote: »
    I think no more distribution tests are needed and I'll put a summary of the scores together soon.

    Maybe one more, if possible. [14,2,7,8] should do poorly and would be a good comparison to the others.
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-17 11:51
    evanh wrote: »
    TonyB_ wrote: »
    Thanks a lot, Evan. zfreq(0) is correct now. Looking just at zfreq, [6,2,3,9] and [6,2,11,6] do very well. Not checked others.

    [6 2 11 6] comes up clean. There is three very poor scores but they all check out as borderline BCFN_FF cases. So, really only a single 256 MB and the rest are 512 MB or better.

    Here's all nine of the every-aperture score tables, and also the extended PR reports for the three borderline cases of [6 2 11 6].

    Thanks, Evan. Have you dropped a couple of candidates recently? Is it the case that the nine consist of the seven with the best scores, plus [14,2,7,5] and [14,2,7,6]?

    The key question: based on PractRand tests which do you think is the best?
  • evanh wrote: »
    potatohead wrote: »
    At some point a useful subset of all this needs to be in the P2 datasheet, along with software code.
    I dunno about putting it in official Prop2 docs but here's the summary topic - https://forums.parallax.com/discussion/168188/xoroshiro-random-number-generator

    I haven't posted the sources in that topic. The testing source code is still evolving in some ways. And Tony has some of his own.

    There is a number of archives in various posts of this topic though.

    I think we should keep using this thread for test results and leave the other topic for general info about the algorithm plus recommended constants.
  • evanh wrote: »
    Here's all nine of the every-aperture score tables, and also the extended PR reports for the three borderline cases of [6 2 11 6].

    It would be useful to have an every-aperture table with all the corrections for borderline cases.
  • evanhevanh Posts: 15,091
    TonyB_ wrote: »
    It would be useful to have an every-aperture table with all the corrections for borderline cases.

    Ha! That won't be happening unless someone fines a way to tell Practrand to ease up on the sensitivity of the BCFN_FF tests.

    You're welcome to hand edit the tables yourself.

  • evanhevanh Posts: 15,091
    TonyB_ wrote: »
    evanh wrote: »
    Here's all nine of the every-aperture score tables, and also the extended PR reports for the three borderline cases of [6 2 11 6].
    Thanks, Evan. Have you dropped a couple of candidates recently? Is it the case that the nine consist of the seven with the best scores, plus [14,2,7,5] and [14,2,7,6]?
    There was plenty more where those came from. The only other candidate I'd being working on lately was the poorly scoring one for comparison.
    The key question: based on PractRand tests which do you think is the best?
    I've been spending a lot more time coding than pondering the results. :)

  • evanh wrote: »
    TonyB_ wrote: »
    It would be useful to have an every-aperture table with all the corrections for borderline cases.

    Ha! That won't be happening unless someone fines a way to tell Practrand to ease up on the sensitivity of the BCFN_FF tests.

    You're welcome to hand edit the tables yourself.

    It would be good if Chris (the PractRand author) could tell us how to modify the BCFN_FF tests. I could edit the tables, but the amended borderline scores are scattered about in different files and I think not all of them have been posted.

    It's interesting that for eight of the nine [a,b,c,d] candidates b = 2, which is a left shift, whereas a, c & d are all left rotates. The exception is [13,5,10,10].
  • evanhevanh Posts: 15,091
    edited 2018-05-17 13:13
    The nine were hand picked from the following table (which I don't seem to have posted before). These are the auto-culled most recent complete run of the full set of candidates:
    __________________________________________________________________________________________________________
      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  7]   512M    4G    2G    2G    2G    1G    1G    1G    1G  512M  512M    1G    1G    1G    1G  512M  512M    1G  512M  512M  512M
    [ 5  2  6  8]   512M    2G    1G    4G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G  512M  512M  512M    1G    1G  512M
    [ 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
    [ 4  8  5  3]   512M    4G    2G    2G    2G  512M  512M  512M  512M  512M    1G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M
    [ 4  8  5  8]   256M    2G    1G    4G    1G    1G  512M    2G  512M  512M  512M  512M  512M    1G  512M  512M  512M  512M  512M    1G    1G
    [ 5  8  4  2]   512M    4G    1G    4G    1G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M
    [ 6 14 11  8]   256M    4G    4G    4G    2G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M
    [ 6 14 11  9]   512M    8G    1G    4G    2G    1G    1G  512M  512M    1G    1G    1G  512M    1G  512M  512M  512M  512M  512M    1G    1G
    [11 14  6  7]   512M    4G    2G    2G    1G  512M    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G  512M
    [11 14  6 12]   512M    4G    2G    4G    1G  512M    1G    1G  512M    1G    1G    1G  512M  512M  512M  512M    1G    1G    1G  512M  512M
    [10  2  7 10]   512M    1G    1G    2G    1G  512M  512M  512M    1G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M
    [10  2  7 12]   512M    2G    1G    4G    1G    1G    1G    1G    1G    1G    1G    1G  512M  512M    1G  512M    1G  512M  512M  512M  512M
    [ 7  2 14 10]   512M    2G    1G    4G    2G    1G    1G  512M  512M    1G  512M  512M  512M  512M    1G  512M  512M  512M  512M  512M  512M
    [13  5  8 10]   512M    4G    2G    4G    2G    1G    1G    1G    1G    1G    1G    1G  512M    1G    1G    1G    1G    1G  512M  512M  512M
    [ 9  2 14  8]   512M    4G    2G    2G    2G  512M  512M  512M  512M  512M    1G  512M    1G  512M  512M    1G  512M  512M  512M  512M  512M
    [14  2  9  7]   512M    4G    1G    2G    1G    1G  512M  512M  512M  512M  512M  512M    1G  512M    1G    1G  512M  512M    1G    1G    1G
    [14  2  9 12]   512M    2G    1G    4G    1G  512M  512M  512M  512M  512M  512M    1G    1G  512M    1G    2G    1G    1G    1G  512M  512M
    [10  3 11 10]   512M    4G    2G    4G    2G    1G    1G  512M  512M    1G    1G  512M  512M    1G  512M  512M  512M  512M  512M  512M  512M
    [ 6  3 15  7]   512M    8G    1G   16G    4G  512M  512M  512M    1G    1G    1G    1G    1G    1G    1G  512M    1G  512M  512M  512M  512M
    [ 6  3 15  8]   512M    2G    2G    2G    1G  512M  512M    1G  512M    1G    1G    1G  512M  512M  512M  512M  512M  512M    1G  512M  512M
    [15  3  6  6]   256M    2G    4G    2G    2G    1G    1G    1G    1G    1G    1G  512M    1G    1G    1G    1G    1G    1G    1G  512M    1G
    [13  5 10  8]   512M    4G    4G    4G    1G  512M  512M    1G    1G    1G    1G    1G    1G    1G    1G  512M    1G    1G  512M  512M  512M
    [13  5 10  9]   512M    4G    4G    4G    2G  512M  512M  512M  512M  512M    1G    1G    1G  512M  512M  512M  512M  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
    [13  5 10 12]   512M    4G    1G    8G    4G    1G  512M    1G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M    1G
    [ 2  8  7  5]   512M    4G    2G    4G    2G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M    1G
    [ 2  8  7  8]   512M    2G    1G    2G    1G    1G    1G    1G    1G    2G    2G    2G    1G    1G    1G    1G    1G  512M  512M  512M  512M
    [ 7  8  2  7]   512M    4G    1G    4G    1G  512M  512M  512M  512M  512M  512M  512M    1G    1G  512M    1G  512M  512M  512M  512M  512M
    [14  8  9 12]   512M    2G    1G    4G    2G  512M  512M  512M  512M    1G    1G    1G  512M    1G  512M  512M    1G    1G    1G    1G  512M
    [11 10 12  8]   512M    2G    1G    2G    1G  512M    1G    1G    1G    1G    1G    1G    1G  512M  512M    1G  512M  512M  512M    1G  512M
    [ 3  2  6  3]   512M    2G    1G    4G    1G    1G  512M    1G    1G    1G    1G  512M  512M  512M  512M    1G  512M  512M    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
    [ 3  2  6  8]   512M    2G    1G    2G    1G  512M  512M  512M    1G  512M  512M    1G  512M  512M  512M  512M  512M  512M  512M  512M  512M
    [ 3  2  6  9]   512M    4G    2G    4G    1G    2G    2G    1G  512M    1G  512M    1G    1G    2G    1G    2G    1G    2G    1G  512M    1G
    [ 6  2  3  6]   512M    4G    1G    4G    1G    1G    1G    1G    1G  512M    1G    1G    1G    1G    2G    1G    1G    1G  512M  512M  512M
    [ 6  2  3  8]   512M    2G    1G    2G    1G    1G    1G    1G    1G    1G    1G    1G    1G    1G  512M    1G    1G    1G    1G    1G  512M
    [ 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  3]   512M    4G    2G    2G    2G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M
    [ 6  2 11  4]   512M    4G    4G    4G    2G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  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
    [ 6  2 11  7]   512M    4G    2G    4G    2G    1G  512M  512M  512M  512M    1G  512M  512M  512M    1G    1G    1G  512M    1G  512M  512M
    [ 6  2 11  8]   512M    4G    1G    2G    1G  512M    1G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M
    [11  2  6  2]   512M    2G    1G    2G    1G  512M    1G    1G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M    1G  512M  512M
    [11  2  6  8]   512M    4G    2G    2G    1G  512M    1G    1G  512M    1G    1G    1G  512M  512M  512M    1G    1G  512M  512M  512M    1G
    [15  7  4  6]   512M    2G    1G    4G    2G  512M    1G    1G    1G  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M  512M
    [13  9  8 10]   512M    4G    1G    4G    1G    1G    1G    1G    1G    1G    1G    1G    1G  512M  512M  512M  512M  512M  512M  512M  512M
    

    EDIT: I note it took only 9 hours to run. That would suggest the culling threshold was set very high, ie: Any scores (except for direct 16+0 aperture) below 512 MB would have terminated the testing of that candidate.
  • We need some simplified scoring method to compare the every-aperture results, maybe mean and standard deviation for each sample size. Another way could be visually, using 16 by 16 "randomgrams".
  • evanh wrote: »
    The nine were hand picked from the following table (which I don't seem to have posted before). <snip>
    EDIT: I note it took only 9 hours to run. That would suggest the culling threshold was set very high, ie: Any scores (except for direct 16+0 aperture) below 512 MB would have terminated the testing of that candidate.

    I wonder how long it would take to run an every-aperture test for all possible [a,b,c,d] candidates (84 * 16 = 1344), then stop each test if a 16-bit sample score is less than 512M? That should weed out most of the duds. Ideally, the BCFN_FF test would be amended first. :)
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-17 13:27
    Or just run the 16 * 16-bit sample tests first, to see how many candidates are left. A 512M threshold would eliminate [14,2,7,5], though.
  • evanhevanh Posts: 15,091
    edited 2018-05-17 13:44
    TonyB_ wrote: »
    I wonder how long it would take to run an every-aperture test for all possible [a,b,c,d] candidates (84 * 16 = 1344) ...
    2000 hours (84 days) without any culling.
    Ideally, the BCFN_FF test would be amended first. :)
    Yeah, I'll have a nosy at the Practrand sources. I'm not likely to solve it myself though.

    This issue has probably already made that culled list above smaller than it should be. It's been present all along but I hadn't gone looking at the report files that closely until the oddball scores really stuck out.

  • TonyB_TonyB_ Posts: 2,099
    edited 2019-12-06 01:42
    evanh wrote: »
    Revised reports attached.

    Here are the processed results for the selected xoroshiro32++ [a,b,c,d] in the reports:

    Pair frequency
    Actual and Expected
    # a,  b,  c,  d,     pfreq0,     pfreq1,     pfreq2,     pfreq3,     pfreq4,     pfreq5,     pfreq6,     pfreq7,     pfreq8,     pfreq9,    pfreq10,    pfreq11,    pfreq12,   pfreq13+
      3,  2,  6,  5, 1579577465, 1580498553,  790225125,  263257382,   65739315,   13130405,    2185011,     310559,      38760,       4247,        439,         32,          2,          1
      5,  2,  6,  9, 1577721906, 1582349741,  791150818,  262958600,   65352861,   12958311,    2134177,     299778,      36801,       3862,        406,         35,          0,          0
      6,  2,  3,  9, 1580730460, 1579315044,  789689377,  263452640,   65972304,   13231825,    2212851,     317581,      40351,       4412,        419,         27,          5,          0
      6,  2,  5,  5, 1575042981, 1585043481,  792485373,  262496631,   64792687,   12712339,    2069227,     285792,      34652,       3752,        351,         28,          2,          0
      6,  2,  5,  9, 1579058325, 1580974428,  790537395,  263175214,   65631824,   13074729,    2164441,     307823,      38449,       4228,        402,         33,          5,          0
      6,  2, 11,  6, 1579034139, 1581029638,  790511294,  263159759,   65640301,   13076446,    2165616,     307324,      38135,       4177,        421,         41,          5,          0
     13,  5, 10, 10, 1578197932, 1581868518,  790926518,  263020052,   65466146,   12999358,    2143902,     303205,      37106,       4115,        406,         35,          3,          0
     14,  2,  7,  5, 1576661053, 1583423321,  791674049,  262776786,   65121487,   12864448,    2110786,     295138,      35867,       3945,        372,         41,          3,          0
     14,  2,  7,  6, 1579336929, 1580735764,  790348643,  263221421,   65684445,   13109945,    2176642,     310656,      38143,       4228,        446,         32,          1,          1
    #expected, , , , 1580030169, 1580030169,  790015084,  263338361,   65834590,   13166918,    2194486,     313498,      39187,       4354,        435,         40,          3,          0
    

    Pair frequency
    |Actual-Expected|/Expected
    # a,  b,  c,  d,     pfreq0,     pfreq1,     pfreq2,     pfreq3,     pfreq4,     pfreq5,     pfreq6,     pfreq7,     pfreq8,     pfreq9,    pfreq10,    pfreq11,    pfreq12
      3,  2,  6,  5, 0.00028651, 0.00029643, 0.00026586, 0.00030750, 0.00144718, 0.00277308, 0.00431763, 0.00937486, 0.01089647, 0.02457510, 0.00919540, 0.20000000, 0.33333333
      5,  2,  6,  9, 0.00146089, 0.00146805, 0.00143761, 0.00144210, 0.00731726, 0.01584326, 0.02748206, 0.04376423, 0.06088753, 0.11299954, 0.06666666, 0.12500000, 1.00000000
      6,  2,  3,  9, 0.00044321, 0.00045260, 0.00041227, 0.00043396, 0.00209181, 0.00492955, 0.00836870, 0.01302400, 0.02970372, 0.01332108, 0.03678160, 0.32500000, 0.66666666
      6,  2,  5,  5, 0.00315638, 0.00317292, 0.00312688, 0.00319638, 0.01582607, 0.03452432, 0.05707896, 0.08837695, 0.11572715, 0.13826366, 0.19310344, 0.30000000, 0.33333333
      6,  2,  5,  9, 0.00061507, 0.00059762, 0.00066114, 0.00061953, 0.00307993, 0.00700156, 0.01369113, 0.01810218, 0.01883277, 0.02893890, 0.07586206, 0.17500000, 0.66666666
      6,  2, 11,  6, 0.00063038, 0.00063256, 0.00062810, 0.00067822, 0.00295116, 0.00687115, 0.01315570, 0.01969390, 0.02684563, 0.04065227, 0.03218390, 0.02500000, 0.66666666
     13,  5, 10, 10, 0.00115962, 0.00116348, 0.00115369, 0.00120874, 0.00559651, 0.01272583, 0.02305050, 0.03283274, 0.05310434, 0.05489205, 0.06666666, 0.12500000, 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
    

    Zero run frequency
    Actual and Expected
    # a,  b,  c,  d,  zero runs,   mean run,     zfreq1,     zfreq2,     zfreq3,     zfreq4,     zfreq5,     zfreq6,     zfreq7,     zfreq8,     zfreq9,    zfreq10,    zfreq11,    zfreq12,    zfreq13,    zfreq14,    zfreq15,    zfreq16,    zfreq17,    zfreq18,    zfreq19,    zfreq20,    zfreq21,   zfreq22+
      3,  2,  6,  5,  998145396, 1.58251239,  630783391,  232225735,   85309325,   31466104,   11584286,    4274071,    1577335,     583136,     215690,      79940,      29376,      10714,       3929,       1488,        538,        213,         70,         28,         16,          7,          3,          1
      5,  2,  6,  9,  999508882, 1.57849713,  632848160,  232401948,   85154345,   31184530,   11388809,    4151904,    1513157,     551534,     200540,      72819,      26274,       9497,       3401,       1272,        425,        164,         63,         28,          9,          2,          1,          0
      6,  2,  3,  9,  998985283, 1.58233608,  631080305,  232610061,   85557191,   31490618,   11553432,    4242365,    1553124,     569770,     208316,      76330,      27898,      10017,       3742,       1371,        493,        157,         61,         19,          7,          5,          0,          1
      6,  2,  5,  5,  998495829, 1.57741568,  632757078,  231935668,   84845771,   31117549,   11346809,    4130947,    1500048,     549004,     199250,      72440,      26289,       9509,       3556,       1222,        459,        150,         48,         20,         11,          1,          0,          0
      6,  2,  5,  9,  999702772, 1.57952780,  632512319,  232553631,   85386929,   31264025,   11435792,    4167941,    1516406,     551069,     200113,      73005,      26369,       9620,       3542,       1286,        476,        171,         49,         22,          5,          1,          1,          0
      6,  2, 11,  6,  999029094, 1.58056872,  631991321,  232268578,   85271519,   31338519,   11492003,    4216159,    1550381,     569920,     209311,      76972,      27992,      10385,       3824,       1394,        498,        194,         76,         31,         12,          4,          1,          0
     13,  5, 10, 10,  998907307, 1.57992430,  631874000,  232477975,   85241804,   31287786,   11441907,    4181970,    1526459,     556126,     203131,      73731,      27202,       9770,       3505,       1219,        443,        176,         61,         31,         10,          0,          1,          0
     14,  2,  7,  5,  999603893, 1.57728582,  633209074,  232494820,   85032136,   31096279,   11317144,    4114211,    1492729,     541039,     195269,      70772,      25843,       9337,       3404,       1195,        418,        142,         50,         17,          9,          3,          1,          1
     14,  2,  7,  6,  998611333, 1.58153315,  631280667,  232302588,   85419904,   31394728,   11532296,    4230888,    1552946,     569943,     207581,      75934,      27833,      10138,       3657,       1397,        516,        202,         70,         29,          7,          5,          4,          0
    #expected, , , ,  998769553, 1.58197670,  631342768,  232258025,   85442952,   31432706,   11563446,    4253954,    1564942,     575710,     211792,      77914,      28663,      10544,       3879,       1427,        525,        193,         71,         26,         10,          4,          1,          0
    

    Zero run frequency
    |Actual-Expected|/Expected
    # a,  b,  c,  d,  zero runs,   mean run,     zfreq1,     zfreq2,     zfreq3,     zfreq4,     zfreq5,     zfreq6,     zfreq7,     zfreq8,     zfreq9,    zfreq10,    zfreq11,    zfreq12,    zfreq13,    zfreq14,    zfreq15,    zfreq16,    zfreq17,    zfreq18,    zfreq19,    zfreq20,    zfreq21
      3,  2,  6,  5, 0.00062492, 0.00033862, 0.00088601, 0.00013902, 0.00156393, 0.00106252, 0.00180223, 0.00472901, 0.00791914, 0.01289885, 0.01840485, 0.02600302, 0.02487527, 0.01612291, 0.01288992, 0.04274702, 0.02476190, 0.10362694, 0.01408450, 0.07692307, 0.60000000, 0.75000000, 2.00000000
      5,  2,  6,  9, 0.00074023, 0.00219950, 0.00238442, 0.00061966, 0.00337777, 0.00789547, 0.01510250, 0.02398944, 0.03309068, 0.04199336, 0.05312759, 0.06539261, 0.08334787, 0.09929817, 0.12322763, 0.10861948, 0.19047619, 0.15025906, 0.11267605, 0.07692307, 0.10000000, 0.50000000, 0.00000000
      6,  2,  3,  9, 0.00021599, 0.00022716, 0.00041572, 0.00151571, 0.00133702, 0.00184241, 0.00086600, 0.00272428, 0.00755171, 0.01031769, 0.01641232, 0.02033010, 0.02668946, 0.04998103, 0.03531838, 0.03924316, 0.06095238, 0.18652849, 0.14084507, 0.26923076, 0.30000000, 0.25000000, 1.00000000
      6,  2,  5,  5, 0.00027406, 0.00288311, 0.00224016, 0.00138792, 0.00698923, 0.01002640, 0.01873464, 0.02891592, 0.04146735, 0.04638793, 0.05921847, 0.07025694, 0.08282454, 0.09816009, 0.08326888, 0.14365802, 0.12571428, 0.22279792, 0.32394366, 0.23076923, 0.10000000, 0.75000000, 1.00000000
      6,  2,  5,  9, 0.00093436, 0.00154800, 0.00185248, 0.00127274, 0.00065567, 0.00536641, 0.01103944, 0.02021954, 0.03101456, 0.04280106, 0.05514372, 0.06300536, 0.08003349, 0.08763277, 0.08687806, 0.09880868, 0.09333333, 0.11398963, 0.30985915, 0.15384615, 0.50000000, 0.75000000, 0.00000000
      6,  2, 11,  6, 0.00025986, 0.00089001, 0.00102725, 0.00004543, 0.00200640, 0.00299646, 0.00617834, 0.00888467, 0.00930449, 0.01005714, 0.01171432, 0.01209025, 0.02340997, 0.01507966, 0.01417891, 0.02312543, 0.05142857, 0.00518134, 0.07042253, 0.19230769, 0.20000000, 0.00000000, 0.00000000
     13,  5, 10, 10, 0.00013792, 0.00129736, 0.00084143, 0.00094700, 0.00235417, 0.00461048, 0.01051062, 0.01692166, 0.02459068, 0.03401712, 0.04089389, 0.05368739, 0.05097163, 0.07340667, 0.09641660, 0.14576033, 0.15619047, 0.08808290, 0.14084507, 0.19230769, 0.00000000, 1.00000000, 0.00000000
     14,  2,  7,  5, 0.00083536, 0.00296520, 0.00295608, 0.00101953, 0.00480807, 0.01070308, 0.02130005, 0.03285014, 0.04614420, 0.06022302, 0.07801522, 0.09166516, 0.09838467, 0.11447268, 0.12245424, 0.16257883, 0.20380952, 0.26424870, 0.29577464, 0.34615384, 0.10000000, 0.25000000, 0.00000000
     14,  2,  7,  6, 0.00015841, 0.00028038, 0.00009836, 0.00019186, 0.00026974, 0.00120823, 0.00269383, 0.00542224, 0.00766545, 0.01001719, 0.01988271, 0.02541263, 0.02895719, 0.03850531, 0.05723124, 0.02102312, 0.01714285, 0.04663212, 0.01408450, 0.11538461, 0.30000000, 0.25000000, 3.00000000
    

    Notes
    pfreq(x) = output pairs that occur x times
    zfreq(x) = zero runs of length x

    If N-1 = full period (2^32-1 for the above) then:

    (a) Expected pfreq(x) = 1/x! * N/e
    (b) Sum of pfreq(x) = N
    (c) Sum of x * pfreq(x) = N-1
    (d) Expected zero runs = (1-1/e) * N/e
    (e) Expected mean zero run = 1/(1-1/e)
    (f) Expected zfreq(x) = (1-1/e)^2 * N/e^x
    (g) Sum of zfreq(x) = zero runs
    (h) Sum of x * zfreq(x) = pfreq(0)
    (i) Sum of x * zfreq(x) / Sum of zfreq(x) = mean zero run

    x >= 0 for pfreq(x), x > 0 for zfreq(x)

    Comments
    These frequency distribution tests are intended as an independent "sanity check" but doing well does not imply the same will happen in other, more rigorous randomness tests. However, these frequency tests can detect certain bad candidates and also act as a "tie-breaker" for good candidates, as is the case here. For example, assuming all other scores are equal, [6,2,5,5] could be eliminated on pair frequency (which is more important in my opinion than zero run frequency).
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-18 01:56
    evanh wrote: »
    I've made a multi-case launching script too. It uses all RAM and creates a lot of smaller files now. I mainly chose this approach because I was wary of many programs concurrently trying to append the same files.
    	// read pair array and increment freq values
    	irng = 0;
    	do {
    		ifreq = pairs[irng++];
    		pfreq[ifreq]++;
    
    		// zero-run freq values
    		if( ifreq == 0 )  ztally++;
    		else {
    			if( ztally != 0 )  zfreq[ztally]++;
    			zfreq[0]++;
    			ztally = 0;
    		}
    	} while( irng );
    

    There is a small error in the above code. If the last byte of the 4GB pair array is zero, then the last zero run will not be written to the zfreq array. Also, it would better if zfreq[0] held the number of zero runs, i.e. it is incremented whenever zfreq[tally] is incremented. I think the amended code could be:
    	// read pair array and increment freq values
    	irng = 0;
    	do {
    		ifreq = pairs[irng++];
    		pfreq[ifreq]++;
    
    		// zero-run freq values
    		if( ifreq == 0 )  ztally++;
    		else
    		{
    			if( ztally != 0 )
    			{
    				zfreq[ztally]++;
    				zfreq[0]++;
    				ztally = 0;
    			}
    		}
    	} while( irng );
    	if( ztally != 0 )
    	{
    		zfreq[ztally]++;
    		zfreq[0]++;
    	}
    
  • The results two posts up are remarkably good. |Actual-Expected|/Expected show this best. The smaller the better and some of the errors are tiny. Note the consistency across pfreq0-pfreq3. I deduced the zero run exponential distribution from the results, I can't prove it!

    I'd like to see how bad candidates perform, e.g. xoroshiro32++ [14,2,7,8] or xoroshiro32+p [14,2,7] or xoroshiro32+ [14,2,7], getting progressively worse. Repeat frequency tests suggests xoroshiro32++ [14,2,7,7] and [14,2,7,9] will be adversely affected by their proximity to [14,2,7,8].
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-18 15:03
    We could run the frequency tests and use pfreq0 to cull candidates before any PractRand culling. For example, |Actual-Expected|/Expected less than 0.001 is achievable, thus the |Actual-Expected| threshold could be set to Expected/1000 = 1580030. In other words, we look for better than 0.999 accuracy (> 99.9%). Harsh, but fair. Record the candidates that pass, then try these with 16-bit sample PractRand tests with minimum threshold 512M. This process should be a lot faster than using PractRand only.
  • ... assuming there are no borderline failures with 16-bit samples.
  • TonyB_TonyB_ Posts: 2,099
    edited 2018-05-26 22:48
    Last week I added a few new things to the frequency test results:

    1. A pfreq13+ value that is the sum of all output pair frequencies of 13 and higher.
    2. A zfreq22+ value that is the sum of all zero run lengths of 22 and higher.
    3. A mean run value for average zero run length, which is the ratio of two sums calculated using test data and therefore arguably the most meaningful zero run result. The relative rankings between different candidates for mean run are very similar to pfreq0-pfreq3, which suggests the latter could be used solely as "tie-breakers".

    Both 1 and 2 are expected to be zero for a good candidate, but could be significantly more than zero for a bad candidate (conjecture in the absence of an actual test).
  • Evan,

    Do you have the full-period constants for any of xoroshiro36/38/40?
  • evanhevanh Posts: 15,091
    Here we go. Not all sorted the same way though. I haven't touched them in a long while. s20 was as large as I got.
  • evanh wrote: »
    Here we go. Not all sorted the same way though. I haven't touched them in a long while. s20 was as large as I got.

    Many thanks, Evan. xoroshiro40 has relatively few full-period constants.

  • evanhevanh Posts: 15,091
    edited 2018-06-04 00:42
    Seems to be correct. s18 is similarly short. The even sizes are a lot shorter than the odds.

    Here's the same run for Xorshift "xs-s20" but including the log file. I don't seem to have kept very many logs.

    EDIT: Looking at the s15 candidate list, it's only 73 lines, which is shorter than the s16 list. That makes the s16 list oddly long at 84 lines.

Sign In or Register to comment.