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 generatorsLCG

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.93RNG = RNG_stdin32, seed = 0x4a992b2ctest set = normal, folding = standard (32 bit)rng=RNG_stdin32, seed=0x4a992b2clength= 64 megabytes (2^26 bytes), time= 2.9 secondsTest Name Raw Processed EvaluationBCFN(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.93RNG = RNG_stdin32, seed = 0x187edf12test set = normal, folding = standard (32 bit)rng=RNG_stdin32, seed=0x187edf12length= 64 megabytes (2^26 bytes), time= 2.9 secondsTest Name Raw Processed EvaluationDC6-9x1Bytes-1 R= +6.3 p = 2.2e-3 unusualGap-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.93RNG = RNG_stdin64, seed = 0xe15bf63ctest set = normal, folding = standard (64 bit)rng=RNG_stdin64, seed=0xe15bf63clength= 128 megabytes (2^27 bytes), time= 2.8 secondsTest 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.93RNG = RNG_stdin64, seed = 0x8c7c5173test set = normal, folding = standard (64 bit)rng=RNG_stdin64, seed=0x8c7c5173length= 128 megabytes (2^27 bytes), time= 2.8 secondsTest 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.93RNG = RNG_stdin64, seed = 0x300dab94test set = normal, folding = standard (64 bit)rng=RNG_stdin64, seed=0x300dab94length= 256 megabytes (2^28 bytes), time= 3.7 secondsno anomalies in 159 test result(s)rng=RNG_stdin64, seed=0x300dab94length= 512 megabytes (2^29 bytes), time= 7.9 secondsTest Name Raw Processed EvaluationBCFN(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=0x300dab94length= 256 gigabytes (2^38 bytes), time= 3857 seconds no anomalies in 265 test result(s)rng=RNG_stdin64, seed=0x300dab94length= 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.93RNG = RNG_stdin64, seed = 0x82f88431test set = normal, folding = standard (64 bit)rng=RNG_stdin64, seed=0x82f88431length= 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 anomaliesrng=RNG_stdin64, seed=0x82f88431length= 256 megabytes (2^28 bytes), time= 4.7 seconds no anomalies in 159 test result(s)rng=RNG_stdin64, seed=0x82f88431length= 512 megabytes (2^29 bytes), time= 9.5 seconds no anomalies in 169 test result(s)...rng=RNG_stdin64, seed=0x82f88431length= 16 terabytes (2^44 bytes), time= 254943 seconds no anomalies in 329 test result(s)