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)

7 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.

Leave a Reply

Your email address will not be published. Required fields are marked *