Testing RNGs with PractRand

PractRand is a random number generator test suite, somewhat like the DIEHARDER and NIST tests I’ve written about before, but more demanding.

Rather than running to completion, it runs until it a test fails with an infinitesimally small p-value. It runs all tests at a given sample size, then doubles the sample and runs the tests again.

32-bit generators

LCG

A while back I wrote about looking for an RNG that would fail the NIST test suite and being surprised that a simple LCG (linear congruential generator) did fairly well. PractRand, however, dismisses this generator with extreme prejudice:

RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0x4a992b2c
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0x4a992b2c
length= 64 megabytes (2^26 bytes), time= 2.9 seconds
Test Name Raw Processed Evaluation
BCFN(2+0,13-3,T) R=+115128 p = 0 FAIL !!!!!!!!
BCFN(2+1,13-3,T) R=+105892 p = 0 FAIL !!!!!!!!
...
[Low1/32]FPF-14+6/16:(8,14-9) R= +25.8 p = 1.5e-16 FAIL
[Low1/32]FPF-14+6/16:(9,14-10) R= +15.5 p = 8.2e-9 very suspicious
[Low1/32]FPF-14+6/16:(10,14-11) R= +12.9 p = 1.8e-6 unusual
[Low1/32]FPF-14+6/16:all R=+380.4 p = 8.2e-337 FAIL !!!!!!!
[Low1/32]FPF-14+6/16:all2 R=+33954 p = 0 FAIL !!!!!!!!
[Low1/32]FPF-14+6/16:cross R= +33.6 p = 6.4e-25 FAIL !!
...and 9 test result(s) without anomalies

I don’t recall the last time I saw a p-value of exactly zero. Presumably the p-value was so small that it underflowed to zero.

MWC

Another 32 bit generator, George Marsaglia’s MWC generator, also fails, but not as spectacularly as LCG.

RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0x187edf12
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0x187edf12
length= 64 megabytes (2^26 bytes), time= 2.9 seconds
Test Name Raw Processed Evaluation
DC6-9x1Bytes-1 R= +6.3 p = 2.2e-3 unusual
Gap-16:A R= +33.3 p = 1.6e-28 FAIL !!!
Gap-16:B R= +13.6 p = 7.9e-12 FAIL
...and 105 test result(s) without anomalies

64-bit generators

Next let’s see how some well-regarded 64-bit random number generators do. We’ll look at xorshift128+ and xoroshir0128+ by Sebastiano Vigna and David Blackman, the famous Mersenne Twister, and PCG by Melissa O’Neill.

The numbers generated by xhoroshir0128+ and xorshift128+ are not random in the least significant bit and so the PractRand tests end quickly. The authors claim that xoroshiro128+ “passes the PractRand test suite up to (and included) 16TB, with the exception of binary rank tests.” I’ve only run PractRand with its default settings; I have not tried getting it to keep running the rest of the tests.

A lack of randomness in the least significant bits is inconsequential if you’re converting the outputs to floating point numbers, say as part of the process of generating Gaussian random values. For other uses, such as reducing the outputs modulo a small number, a lack of randomness in the least significant bits would be disastrous. (Here numerical analysis and number theory have opposite ideas regarding which parts of a number are most “significant.”)

At the time of writing, both Mersenne Twister and PCG have gone through 256 GB of generated values and are still running. I intend to add more results tomorrow.

Update: Mersenne Twister failed a couple of tests with 512 GB of input. I stopped the tests after PCG passed 16 TB.

xoroshiro128+

RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0xe15bf63c
test set = normal, folding = standard (64 bit)

rng=RNG_stdin64, seed=0xe15bf63c
length= 128 megabytes (2^27 bytes), time= 2.8 seconds
Test Name Raw Processed Evaluation
[Low1/64]BRank(12):256(2) R= +3748 p~= 3e-1129 FAIL !!!!!!!!
[Low1/64]BRank(12):384(1) R= +5405 p~= 3e-1628 FAIL !!!!!!!!
...and 146 test result(s) without anomalies

xorshift128+

RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0x8c7c5173
test set = normal, folding = standard (64 bit)

rng=RNG_stdin64, seed=0x8c7c5173
length= 128 megabytes (2^27 bytes), time= 2.8 seconds
Test Name Raw Processed Evaluation
[Low1/64]BRank(12):256(2) R= +3748 p~= 3e-1129 FAIL !!!!!!!!
[Low1/64]BRank(12):384(1) R= +5405 p~= 3e-1628 FAIL !!!!!!!!
...and 146 test result(s) without anomalies

Mersenne Twister

RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0x300dab94
test set = normal, folding = standard (64 bit)

rng=RNG_stdin64, seed=0x300dab94
length= 256 megabytes (2^28 bytes), time= 3.7 seconds
no anomalies in 159 test result(s)

rng=RNG_stdin64, seed=0x300dab94
length= 512 megabytes (2^29 bytes), time= 7.9 seconds
Test Name Raw Processed Evaluation
BCFN(2+2,13-2,T) R= -7.0 p =1-1.2e-3 unusual
[Low1/64]BCFN(2+2,13-6,T) R= -5.7 p =1-1.0e-3 unusual
...and 167 test result(s) without anomalies

...

rng=RNG_stdin64, seed=0x300dab94
length= 256 gigabytes (2^38 bytes), time= 3857 seconds
  no anomalies in 265 test result(s)

rng=RNG_stdin64, seed=0x300dab94
length= 512 gigabytes (2^39 bytes), time= 8142 seconds
 Test Name Raw Processed Evaluation
 BRank(12):24K(1) R=+99759 p~= 0 FAIL !!!!!!!!
 [Low16/64]BRank(12):16K(1) R= +1165 p~= 1.3e-351 FAIL !!!!!!!
 ...and 274 test result(s) without anomalies

PCG

RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0x82f88431
test set = normal, folding = standard (64 bit)

rng=RNG_stdin64, seed=0x82f88431
length= 128 megabytes (2^27 bytes), time= 2.0 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/64]DC6-9x1Bytes-1           R=  +6.6  p =  1.6e-3   unusual
  ...and 147 test result(s) without anomalies

rng=RNG_stdin64, seed=0x82f88431
length= 256 megabytes (2^28 bytes), time= 4.7 seconds
  no anomalies in 159 test result(s)

rng=RNG_stdin64, seed=0x82f88431
length= 512 megabytes (2^29 bytes), time= 9.5 seconds
  no anomalies in 169 test result(s)

...

rng=RNG_stdin64, seed=0x82f88431
length= 16 terabytes (2^44 bytes), time= 254943 seconds
  no anomalies in 329 test result(s)

PractRand testing

If you would like someone to run PractRand or other RNG test suites for you and help you understand the results, let’s talk.

10 thoughts on “Testing RNGs with PractRand

  1. I tried PractRand with a lesser known generator, v3b. To be clear, I am not the author of v3b.

    Results seem OK up to 16GB

    RNG_test using PractRand version 0.93
    RNG = RNG_stdin64, seed = 0x6a3ce51b
    test set = normal, folding = standard (64 bit)

    rng=RNG_stdin64, seed=0x6a3ce51b
    length= 128 megabytes (2^27 bytes), time= 3.2 seconds
    no anomalies in 148 test result(s)

    rng=RNG_stdin64, seed=0x6a3ce51b
    length= 256 megabytes (2^28 bytes), time= 7.2 seconds
    no anomalies in 159 test result(s)

    rng=RNG_stdin64, seed=0x6a3ce51b
    length= 512 megabytes (2^29 bytes), time= 14.4 seconds
    Test Name Raw Processed Evaluation
    [Low16/64]BCFN(2+1,13-3,T) R= +8.6 p = 7.1e-4 unusual
    …and 168 test result(s) without anomalies

    rng=RNG_stdin64, seed=0x6a3ce51b
    length= 1 gigabyte (2^30 bytes), time= 27.9 seconds
    no anomalies in 180 test result(s)

    rng=RNG_stdin64, seed=0x6a3ce51b
    length= 2 gigabytes (2^31 bytes), time= 54.3 seconds
    no anomalies in 191 test result(s)

    rng=RNG_stdin64, seed=0x6a3ce51b
    length= 4 gigabytes (2^32 bytes), time= 106 seconds
    no anomalies in 201 test result(s)

    rng=RNG_stdin64, seed=0x6a3ce51b
    length= 8 gigabytes (2^33 bytes), time= 211 seconds
    no anomalies in 212 test result(s)

    rng=RNG_stdin64, seed=0x6a3ce51b
    length= 16 gigabytes (2^34 bytes), time= 419 seconds
    no anomalies in 223 test result(s)

  2. Thanks. I’ve been toying with Dave Thomas’ MWC64X, an un-peer-reviewed 32 bit generator with a period of 2^63 designed for GPUs, and wanted to eventually do a little testing. Here’s a start:

    RNG_test using PractRand version 0.93
    RNG = RNG_stdin32, seed = 0xdf0d180c
    test set = normal, folding = standard (32 bit)

    rng=RNG_stdin32, seed=0xdf0d180c
    length= 4 gigabytes (2^32 bytes), time= 103 seconds
    Test Name Raw Processed Evaluation
    [Low8/32]FPF-14+6/16:cross R= -2.2 p =1-1.0e-3 unusual
    …and 155 test result(s) without anomalies

    rng=RNG_stdin32, seed=0xdf0d180c
    length= 64 gigabytes (2^36 bytes), time= 1640 seconds
    Test Name Raw Processed Evaluation
    [Low8/32]BCFN(2+2,13-0,T) R= +7.2 p = 2.2e-3 unusual
    …and 188 test result(s) without anomalies

    rng=RNG_stdin32, seed=0xdf0d180c
    length= 128 gigabytes (2^37 bytes), time= 3295 seconds
    no anomalies in 196 test result(s)

    I cut out the tests that passed with no anomalies, except for the last one. A couple hiccups so far, but it hasn’t failed yet.

  3. Re: Bob Jenkins’ small generator. I’ve tested it a lot, never seen a problem. So have lots of other people, including the author of PractRand. I’m pretty sure this generator has been tested with PractRand before, at much longer than a terabyte. What is going on here? Broken implementation of the generator? Or a new version of PractRand much tougher than the last one tested? Chris, are you reading? Any comment?

  4. Hi, Don. Re Bob Jenkins’ small generator. Did you know PractRand has a builtin version of this? Probably faster than piping from an external program. Also, do you know the seed used by the generator in the report you link to? If there is a real problem here, i think it must be seed dependent.

    I hadn’t noticed V3b before. Will have a look now. Thanks.

  5. The 32 and 64 bit versions of Bob Jenkins small fast non-cryptographic PRNG passes everything I’ve tried (which is quite a bit). If I scale it down to 16 bit integers it fails after a very long time (16 terabytes, several days of testing), but that might just be poor choice of shift constants on my part, I haven’t checked exhaustively. I have no clue why this guy is seeing failures with my test after a single terabyte.

    Actually, I’ve seen several incidents lately with people testing PRNGs that I know, using my own tests, and getting results that look weird to me. Here’s someone testing mitchell-moore on PractRand I saw a few days ago: https://github.com/lemire/testingRNG/blob/master/practrand/results/testmitchellmoore.log
    He sees it failing BRank, which seems plausible, but at that test length it should fail BCFN too. He does incorrectly tell PractRand it’s a 64 bit PRNG, but that shouldn’t be enough to hide its flaws from BCFN.

  6. Just in case anyone is curious to find out how ‘bad’ MT is compared to other PRNGs… it is one of the few that fails PractRand ~75x faster (~2 minutes!) when using these switches: stdin -tf 2 -te 1 -tlmin 1KB -multithreaded

    RNG_test using PractRand version 0.93
    RNG = mt19937, seed = 0x303d456
    test set = expanded, folding = extra

    rng=mt19937, seed=0x303d456
    length= 1 kilobyte (2^10 bytes), time= 0.4 seconds
    no anomalies in 14 test result(s)

    … no anomalies until:

    rng=mt19937, seed=0x303d456
    length= 4 gigabytes (2^32 bytes), time= 124 seconds
    Test Name Raw Processed Evaluation
    [Low4/16]BRank(18):6K(1) R= +3016 p~= 6.7e-909 FAIL !!!!!!!
    [Low4/32]BCFN_FF(2+1,13-1,T) R= +9.2 p = 1.9e-4 unusual
    …and 1154 test result(s) without anomalies

    Many other PRNGs will fail no more than 2x to 4x faster (time-wise) with those same switch settings. I’m guessing that most people assume that because it runs at about half-speed (GB/s-wise) with those settings that it is not worth it. I conjecture that it is worth it for establishing hard limits on the range of any good PRNGs (until a better tool than PractRand comes along).

    In reply to above post concerning failures that should have shown up, but didn’t: That certainly can happen when you mistakenly specify stdin64 with with Standard Foldings-Normal Test Set (defaults), but not (that I’ve seen) with stdin-Extra Foldings-Expanded Test Set (my recommended settings).

  7. [QUOTE]
    > In reply to above post concerning failures that should have shown up, but didn’t: That certainly can happen when you mistakenly specify stdin64 with with Standard Foldings-Normal Test Set (defaults), but not (that I’ve seen) with stdin-Extra Foldings-Expanded Test Set (my recommended settings).
    [/QUOTE]
    I investigated a little on some of those cases, posted my results here:
    https://sourceforge.net/p/pracrand/discussion/366935/thread/20eff9f1/
    basically:
    – the test on jsf32, I have no clue, my best guess is that he tested a different PRNG by the same author (who often doesn’t name his PRNGs)
    – the test on Mitchell-Moore – he and I were testing different algoritms by the same (co)authors
    – the test on ChaCha, she used an odd number of rounds on an implementation that did not support an odd number of rounds

  8. A 32 bit MWC (lag-1) generator should not fail PractRand that soon. Did you use a poorly chosen multiplier (like those published at Wikipedia) ?
    Try 3658429584 (will pass PractRand > 1 TB).

    Lagged MWC’s (32 and 64 bit) pass PractRand and TestU01 BigCrush (and are as fast as xoshiro256**).

  9. Alexander Pukall

    If you want to test my PRNG, it’s based on the mix : LFSR 64 + LCG 64. Test up to 2TB with Practrand. And mathematically we know that it will give 2^64 random bits.

    // Alexander PUKALL PRNG 64
    // LSFR 64 + LCG 64
    // 128 bits seed
    // prng64.c

    // The output will be 2^64 random bits

    // With lfsr seed = 0xffffffffffffffff
    // and lcg seed = 0xffffffffffffffff
    // the 50 first bytes are
    // 83 CA C9 DF F3 82 B1 EB 1D 2D A2 6A 08 A4 7C 58 99 EB 8A 4F
    // 99 B0 43 01 66 66 49 EC 77 C2 6E 91 6E E0 28 58 DD EF 5D 9D
    // BE F4 DF 57 1D 27 CA B4 2B 16

    // Practrand test : ./prng64 | /rng_test stdin8
    // All tests OK (no anomalies), test with 2TB

    #include <stdint.h>
    #include <stdio.h>

    int main()
    {
    uint64_t lfsr = 0xffffffffffffffffu; //LFSR 64 seed from 0x1 to 0xffffffffffffffff
    uint64_t b=0xffffffffffffffffu; //LCG 64 sedd from 0x0 to 0xffffffffffffffff
    uint8_t rndbyte,tmp,shift;
    int i,q,w;

    if (lfsr==0) lfsr=1; // never 0 in an LFSR

    for (i=0;i<64;i++) // mix LFSR 64 times before use
    {
    rndbyte=0;
    for (q=0;q<8;q++)
    {
    uint64_t msb= lfsr & 0x8000000000000000;
    lfsr <<= 1;

    if (msb==0x8000000000000000) lfsr ^= 0x7287db1e3afac4f1u;
    }
    }

    while(1)
    {
    b=(b*0x5851f42d4c957f2d)+1;

    for (w=0;w<4;w++)
    {
    rndbyte=0;
    for (q=0;q<8;q++)
    {
    uint64_t msb= lfsr & 0x8000000000000000;
    lfsr <<= 1;
    if (msb==0x8000000000000000)
    {
    lfsr ^= 0x7287db1e3afac4f1u;
    tmp=1;
    }
    else
    {
    tmp=0;
    }

    rndbyte=rndbyte+(tmp<<q);
    }

    shift=48-(8*w);
    rndbyte=rndbyte+((b>>shift)& 0xff);

    printf("%c",rndbyte);
    }

    }

    return(0);

    }

Comments are closed.