# PCG Passes PractRand

There were various questions that people asked when PCG first started being discussed on the Internet; one those questions was whether I had also tested PCG with PractRand. I hadn't. I had done my testing using TestU01, which is considered by most to be the “gold standard”, with the broadest range of tests. Back in 2014, PractRand hadn't been on my radar, but looking into it I discovered that it is TestU01's closest competitor. I put testing with PractRand on my to-do list, but it wasn't a very high priority because I knew that all my PCG family members had been designed to pass TestU01's BigCrush test battery with plenty of headroom, which gave me good reason to believe they would do well in any set of statistical tests.

Finally, this summer I was discussing the best practices for testing random number generators with a colleague and I realized that it was high time for me to finally get around to testing PCG (and a few other recent PRNGs, too!). The short version is, it passes just fine. But for the details, read on…

### How Random Number Generator Testing Works

PRNG test suites work by performing some statistically well-understood task using a candidate generator and then checking the plausibility of the results. For example, we could simulate the Birthday Problem, where we keep adding people to a room until two people have the same birthday, and then count how many people we needed. The mathematics of this problem is well understood, so we know exactly how probable every outcome is. A generator that repeated “42” forever would fail this test because repeats (“the same birthday”) occur far too often, as would a generator which never allowed any number to repeat (not enough repeats), as would a generator where repeats happened with the exact same gap between every repeat (incorrect distribution for repeats).

There are a large number of possible tests, some based on familiar ideas like the birthday problem or hands of poker, and others that are more abstruse. It is not uncommon for a generator to pass many tests in a test battery but be tripped up by just one family of tests.

Much like experiments in other fields of science, these tests typically produce a p-value, but whereas scientists usually desire results where the null hypothesis—that the observations were merely due to chance—is ruled out, we desire the opposite: a result confirming that the observed behavior is consistent with chance.

It's in the nature of random number generation that if you run enough tests enough times, you'll sometimes have test outcomes that amount to a “one in a thousand” or even “one in a million” event, but these kinds of failures are easily separated from genuine problems because real problems get worse and worse the more we test, whereas the occasional improbable result won't recur through extended or repeated testing.

### Installation and Use; PractRand vs TestU01

It turns out that TestU01 and PractRand are quite complementary.

#### TestU01

TestU01 comes with an academic paper and two user manuals (a basic one and an advanced one). It compiles to a library and users must understand the TestU01 API in order to use it. In practice, to use the various test batteries TestU01 provides, we just need to understand one function, `unif01_CreateExternGenBits`. We pass it a function that generates a 32-bit unsigned int and the name of the generator, and then pass the `unif01_Gen*` object it returns on to the test battery we wish to use, such as `bbattery_BigCrush`.

TestU01 is not very hard to interface with in theory, but in practice there are a few gotchas. It is designed to test at most 32 bits and some tests use fewer. And it tends to be most sensitive to issues in the high/most-significant bits rather than the low/least-significant bits. (Some users have thought that because it also provides a function `unif01_CreateExternGen01` for generators that return floating point `double` value in the range of 0–1 that this function would use all 48 bits of the floating-point mantissa but that is not the case.)

Thus even when testing 32-bit values, it is important to run two tests, a regular test and a test with a modified version of the PRNG that returns its bits flipped into reverse order.

When the Crush batteries finish, they write a summary. For example, a successful pair of Small Crush runs looks like this:

``````
========= Summary results of SmallCrush =========

Version:          TestU01 1.2.3
Generator:        32-bit WELLRNG512a
Number of statistics:  15
Total CPU time:   00:00:07.82

All tests were passed

``````
``````
========= Summary results of SmallCrush =========

Version:          TestU01 1.2.3
Generator:        32-bit WELLRNG512a [Reversed]
Number of statistics:  15
Total CPU time:   00:00:09.10

All tests were passed

``````

and a failure looks like this:

``````
========= Summary results of SmallCrush =========

Version:          TestU01 1.2.3
Generator:        32-bit MINSTD LCG
Number of statistics:  15
Total CPU time:   00:00:10.05
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  BirthdaySpacings                 eps
2  Collision                      1 - eps1
6  MaxOft                           eps
----------------------------------------------
All other tests were passed

``````

For generators that produce 64-bit values, we must generate at least four variations to return the high 32 bits, the low 32 bits, and each of these reversed. Even there, it is not clear whether there might be some unfortunate correlation between the top half and the bottom half of the 64-bit value that this “half at a time” approach examines, so perhaps we should also add two more variants, a version that alternates the high-32 and low-32 bits and its reversed version.

Because 64-bit generators are difficult to test with much certainty in TestU01, I strongly recommend that creators of 64-bit generators make sure that their generation scheme is scalable to smaller sizes, allowing them to test cut-down 32-bit versions that use half as much memory for generator state. That way TestU01 can have a more holistic view of a smaller-scale generator. If the smaller-scale generator passes TestU01's tests, we have much more reason to be confident about its larger sibling.

TestU01 is capable of far more than just running its crush batteries. There are more detailed interfaces to individual tests. For example, as I mentioned in the PCG paper, the linear complexity test (which a number of generators fail, including some of L'Ecuyer's generators) was inexplicably omitted from Small Crush, so my testing program has an option to directly call the linear complexity test, running it at four different sizes, instead of running one of the crush benchmarks. Here's are the results of the first of those calls:

``````***********************************************************
HOST = satsuki.local, Darwin

32-bit WELLRNG512a

scomp_LinearComp test:
-----------------------------------------------
N =  1,  n = 5000,  r =  0,    s = 1

-----------------------------------------------
Number of degrees of freedom          :    5
Chi2 statistic for size of jumps      :    3.76
p-value of test                       :    0.58

-----------------------------------------------
Normal statistic for number of jumps  :  -40.14
p-value of test                       : 1 - eps1    *****

-----------------------------------------------
CPU time used                    :  00:00:00.00

Generator state:

``````

As you can see, individual test results are more detailed than the Crush test battery results. The failure of the test is marked by the asterisks. The other three tests fail similarly. (Running all four tests took less than 0.1 of a second to run, so it would not have significantly slowed to Small Crush to have included some linear-complexity testing.)

In summary, TestU01 is well documented, powerful, and fairly easy to use, but it is also a little tricky to use well and a little sketchy when it comes to testing 64-bit generators.

#### PractRand

In contrast, PractRand is more sparsely documented and connecting a preexisting random number generator into its C++ code is more complex, but doing so is not actually necessary because it will happily read a binary stream of random numbers from standard input.

Thus, it is even easier to run tests than it is with TestU01. In fact, we can test macOS's `/dev/random` (a special “device file” that outputs nondeterministic cryptographically secure randomness using the Yarrow PRNG) by just running a simple command:

``````macOS\$ ./RNG_test stdin < /dev/random
RNG_test using PractRand version 0.93
RNG = RNG_stdin, seed = 0x906c8753
test set = normal, folding = standard(unknown format)

rng=RNG_stdin, seed=0x906c8753
length= 32 megabytes (2^25 bytes), time= 3.9 seconds
no anomalies in 130 test result(s)

rng=RNG_stdin, seed=0x906c8753
length= 64 megabytes (2^26 bytes), time= 8.3 seconds
no anomalies in 139 test result(s)

rng=RNG_stdin, seed=0x906c8753
length= 128 megabytes (2^27 bytes), time= 16.4 seconds
Test Name                         Raw       Processed     Evaluation
Gap-16:A                          R=  +4.9  p =  1.1e-3   unusual
...and 150 test result(s) without anomalies

rng=RNG_stdin, seed=0x906c8753
length= 256 megabytes (2^28 bytes), time= 32.5 seconds
no anomalies in 162 test result(s)

rng=RNG_stdin, seed=0x906c8753
length= 512 megabytes (2^29 bytes), time= 63.0 seconds
no anomalies in 171 test result(s)

rng=RNG_stdin, seed=0x906c8753
length= 1 gigabyte (2^30 bytes), time= 122 seconds
no anomalies in 183 test result(s)

^C
``````

Compared to TestU01, there are a few things to notice. TestU01's various Crush test batteries run silently for a period of time (a few hours for Big Crush) and then output their results. In contrast, PractRand starts telling you what it's seeing almost immediately and issues a report every time it has seen twice as much data as the last time it made a report.

Also, PractRand is oriented towards receiving a bytestream. It doesn't mind if the generators are 32-bit, 64-bit, 128-bit, or something more unusual like 72-bit or 96-bit. (Although it does benefit from knowing that the generator is producing 32- or 64-bit chunks.)

Finally, we can see that one test reported a result that was slightly unlikely from a statistical perspective but the blip vanished as testing continued.

I stopped the test interactively after 1 GB by pressing Control-C. By default PractRand will keep going until it has tested 32 TB of output. If 1 GB takes 122 seconds, then it'll take 46 days to finish the test! Might as well stop it now.

For fun let's try another Unix special file, `/dev/zero`, which outputs zeros forever:

``````macOS\$ \$ ./RNG_test stdin < /dev/zero
RNG_test using PractRand version 0.93
RNG = RNG_stdin, seed = 0xbbfee72
test set = normal, folding = standard(unknown format)

rng=RNG_stdin, seed=0xbbfee72
length= 128 megabytes (2^27 bytes), time= 2.4 seconds
Test Name                         Raw       Processed     Evaluation
BCFN(2+0,13-3,T)                  R=+17706724 p = 0           FAIL !!!!!!!!
BCFN(2+1,13-3,T)                  R=+8369402 p = 0           FAIL !!!!!!!!
BCFN(2+2,13-3,T)                  R=+4018669 p = 0           FAIL !!!!!!!!
BCFN(2+3,13-3,T)                  R=+1951923 p = 0           FAIL !!!!!!!!
BCFN(2+4,13-4,T)                  R=+1217378 p = 0           FAIL !!!!!!!!
BCFN(2+5,13-5,T)                  R=+754738 p = 0           FAIL !!!!!!!!
BCFN(2+6,13-5,T)                  R=+373439 p = 0           FAIL !!!!!!!!
BCFN(2+7,13-6,T)                  R=+229795 p = 0           FAIL !!!!!!!!
BCFN(2+8,13-6,T)                  R=+114286 p = 0           FAIL !!!!!!!!
BCFN(2+9,13-7,T)                  R=+69277  p = 0           FAIL !!!!!!!!
BCFN(2+10,13-8,T)                 R=+41033  p = 0           FAIL !!!!!!!!
BCFN(2+11,13-8,T)                 R=+20468  p =  1e-5195    FAIL !!!!!!!!
BCFN(2+12,13-9,T)                 R=+11745  p =  3e-2640    FAIL !!!!!!!!
BCFN(2+13,13-9,T)                 R= +5857  p =  4e-1317    FAIL !!!!!!!!
DC6-9x1Bytes-1                    R=+10806727 p = 0           FAIL !!!!!!!!
Gap-16:A                          R=+3583824 p = 0           FAIL !!!!!!!!
Gap-16:B                          R=+16048500 p = 0           FAIL !!!!!!!!
FPF-14+6/16:cross                 R=+294195018 p = 0           FAIL !!!!!!!!
BRank(12):128(4)                  R= +5300  p~=  1e-2819    FAIL !!!!!!!!
BRank(12):256(4)                  R=+10811  p~=  1e-5750    FAIL !!!!!!!!
BRank(12):384(1)                  R= +8161  p~=  1e-2457    FAIL !!!!!!!!
BRank(12):512(2)                  R=+15438  p~=  2e-4648    FAIL !!!!!!!!
BRank(12):768(1)                  R=+16427  p~=  3e-4946    FAIL !!!!!!!!
BRank(12):1K(2)                   R=+31025  p~=  1e-9340    FAIL !!!!!!!!
BRank(12):1536(1)                 R=+32960  p~=  4e-9923    FAIL !!!!!!!!
[Low1/8]BCFN(2+0,13-5,T)          R=+3546530 p = 0           FAIL !!!!!!!!
[Low1/8]BCFN(2+1,13-5,T)          R=+1676322 p = 0           FAIL !!!!!!!!
[Low1/8]BCFN(2+2,13-5,T)          R=+804897 p = 0           FAIL !!!!!!!!
[Low1/8]BCFN(2+3,13-5,T)          R=+390941 p = 0           FAIL !!!!!!!!
[Low1/8]BCFN(2+4,13-6,T)          R=+237394 p = 0           FAIL !!!!!!!!
[Low1/8]BCFN(2+5,13-6,T)          R=+116954 p = 0           FAIL !!!!!!!!
[Low1/8]BCFN(2+6,13-7,T)          R=+70419  p = 0           FAIL !!!!!!!!
[Low1/8]BCFN(2+7,13-8,T)          R=+41511  p = 0           FAIL !!!!!!!!
[Low1/8]BCFN(2+8,13-8,T)          R=+20637  p =  2e-5238    FAIL !!!!!!!!
[Low1/8]BCFN(2+9,13-9,T)          R=+11814  p =  1e-2655    FAIL !!!!!!!!
[Low1/8]BCFN(2+10,13-9,T)         R= +5881  p =  1e-1322    FAIL !!!!!!!!
[Low1/8]DC6-9x1Bytes-1            R=+1591281 p = 0           FAIL !!!!!!!!
[Low1/8]Gap-16:A                  R=+604230 p = 0           FAIL !!!!!!!!
[Low1/8]Gap-16:B                  R=+2770854 p = 0           FAIL !!!!!!!!
[Low1/8]FPF-14+6/16:cross         R=+33904284 p = 0           FAIL !!!!!!!!
[Low1/8]BRank(12):128(4)          R= +5300  p~=  1e-2819    FAIL !!!!!!!!
[Low1/8]BRank(12):256(2)          R= +7644  p~=  3e-2302    FAIL !!!!!!!!
[Low1/8]BRank(12):384(1)          R= +8161  p~=  1e-2457    FAIL !!!!!!!!
[Low1/8]BRank(12):512(2)          R=+15438  p~=  2e-4648    FAIL !!!!!!!!
[Low1/8]BRank(12):768(1)          R=+16427  p~=  3e-4946    FAIL !!!!!!!!
[Low4/32]BCFN(2+0,13-5,T)         R=+3546530 p = 0           FAIL !!!!!!!!
[Low4/32]BCFN(2+1,13-5,T)         R=+1676322 p = 0           FAIL !!!!!!!!
[Low4/32]BCFN(2+2,13-5,T)         R=+804897 p = 0           FAIL !!!!!!!!
[Low4/32]BCFN(2+3,13-5,T)         R=+390941 p = 0           FAIL !!!!!!!!
[Low4/32]BCFN(2+4,13-6,T)         R=+237394 p = 0           FAIL !!!!!!!!
[Low4/32]BCFN(2+5,13-6,T)         R=+116954 p = 0           FAIL !!!!!!!!
[Low4/32]BCFN(2+6,13-7,T)         R=+70419  p = 0           FAIL !!!!!!!!
[Low4/32]BCFN(2+7,13-8,T)         R=+41511  p = 0           FAIL !!!!!!!!
[Low4/32]BCFN(2+8,13-8,T)         R=+20637  p =  2e-5238    FAIL !!!!!!!!
[Low4/32]BCFN(2+9,13-9,T)         R=+11814  p =  1e-2655    FAIL !!!!!!!!
[Low4/32]BCFN(2+10,13-9,T)        R= +5881  p =  1e-1322    FAIL !!!!!!!!
[Low4/32]DC6-9x1Bytes-1           R=+1591281 p = 0           FAIL !!!!!!!!
[Low4/32]Gap-16:A                 R=+604230 p = 0           FAIL !!!!!!!!
[Low4/32]Gap-16:B                 R=+2770854 p = 0           FAIL !!!!!!!!
[Low4/32]FPF-14+6/16:cross        R=+33904284 p = 0           FAIL !!!!!!!!
[Low4/32]BRank(12):128(4)         R= +5300  p~=  1e-2819    FAIL !!!!!!!!
[Low4/32]BRank(12):256(2)         R= +7644  p~=  3e-2302    FAIL !!!!!!!!
[Low4/32]BRank(12):384(1)         R= +8161  p~=  1e-2457    FAIL !!!!!!!!
[Low4/32]BRank(12):512(2)         R=+15438  p~=  2e-4648    FAIL !!!!!!!!
[Low4/32]BRank(12):768(1)         R=+16427  p~=  3e-4946    FAIL !!!!!!!!
[Low1/32]BCFN(2+0,13-6,T)         R=+1099294 p = 0           FAIL !!!!!!!!
[Low1/32]BCFN(2+1,13-6,T)         R=+519590 p = 0           FAIL !!!!!!!!
[Low1/32]BCFN(2+2,13-6,T)         R=+249477 p = 0           FAIL !!!!!!!!
[Low1/32]BCFN(2+3,13-6,T)         R=+121164 p = 0           FAIL !!!!!!!!
[Low1/32]BCFN(2+4,13-7,T)         R=+72212  p = 0           FAIL !!!!!!!!
[Low1/32]BCFN(2+5,13-8,T)         R=+42258  p = 0           FAIL !!!!!!!!
[Low1/32]BCFN(2+6,13-8,T)         R=+20899  p =  5e-5305    FAIL !!!!!!!!
[Low1/32]BCFN(2+7,13-9,T)         R=+11920  p =  1e-2679    FAIL !!!!!!!!
[Low1/32]BCFN(2+8,13-9,T)         R= +5918  p =  6e-1331    FAIL !!!!!!!!
[Low1/32]DC6-9x1Bytes-1           R=+483643 p = 0           FAIL !!!!!!!!
[Low1/32]Gap-16:A                 R=+223041 p = 0           FAIL !!!!!!!!
[Low1/32]Gap-16:B                 R=+888483 p = 0           FAIL !!!!!!!!
[Low1/32]FPF-14+6/16:cross        R=+7961869 p = 0           FAIL !!!!!!!!
[Low1/32]BRank(12):128(2)         R= +3748  p~=  3e-1129    FAIL !!!!!!!!
[Low1/32]BRank(12):256(2)         R= +7644  p~=  3e-2302    FAIL !!!!!!!!
[Low1/32]BRank(12):384(1)         R= +8161  p~=  1e-2457    FAIL !!!!!!!!
[Low1/32]BRank(12):512(1)         R=+10916  p~=  3e-3287    FAIL !!!!!!!!
``````

We can see that PractRand is very unhappy with tons of failures. PractRand actually varies the number of exclamation marks based on the severity of the failure. Obviously all zeros all the time causes very severe failures. The names of the tests are a little cryptic, but they are described on the PractRand website.

That example was a pretty ridiculously extreme fail, so I'll also show you the results from a test of a couple of bad PRNGs to show what more typical fails might look like:

``````linux\$ ./bad-64bit-rng1 | ./RNG_test stdin64
RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0xfecb5683
test set = normal, folding = standard (64 bit)

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

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

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

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

rng=RNG_stdin64, seed=0xfecb5683
length= 2 gigabytes (2^31 bytes), time= 36.5 seconds
Test Name                         Raw       Processed     Evaluation
[Low4/64]FPF-14+6/16:(0,14-0)     R=  +6.3  p =  1.9e-5   unusual
[Low4/64]FPF-14+6/16:(1,14-0)     R=  +6.2  p =  2.6e-5   unusual
[Low4/64]FPF-14+6/16:all          R=  +7.5  p =  1.5e-6   suspicious
[Low4/64]FPF-14+6/16:all2         R=  +9.6  p =  3.1e-5   mildly suspicious
...and 187 test result(s) without anomalies

rng=RNG_stdin64, seed=0xfecb5683
length= 4 gigabytes (2^32 bytes), time= 71.7 seconds
Test Name                         Raw       Processed     Evaluation
[Low16/64]FPF-14+6/16:all         R=  +7.8  p =  8.4e-7   very suspicious
[Low4/64]FPF-14+6/16:(0,14-0)     R= +10.4  p =  3.0e-9   very suspicious
[Low4/64]FPF-14+6/16:(1,14-0)     R=  +9.5  p =  2.0e-8   very suspicious
[Low4/64]FPF-14+6/16:all          R= +12.3  p =  4.9e-11   VERY SUSPICIOUS
[Low4/64]FPF-14+6/16:all2         R= +33.1  p =  1.7e-14    FAIL
[Low1/64]FPF-14+6/16:cross        R=  +9.3  p =  1.7e-8   very suspicious
...and 195 test result(s) without anomalies
``````
``````linux\$ ./bad-64bit-rng2 | ./RNG_test stdin64
RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0x72e95cf7
test set = normal, folding = standard (64 bit)

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

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

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

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

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

rng=RNG_stdin64, seed=0x72e95cf7
length= 4 gigabytes (2^32 bytes), time= 71.4 seconds
Test Name                         Raw       Processed     Evaluation
[Low16/64]Gap-16:B                R=  +4.1  p =  2.0e-3   unusual
...and 200 test result(s) without anomalies

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

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

rng=RNG_stdin64, seed=0x72e95cf7
length= 32 gigabytes (2^35 bytes), time= 578 seconds
no anomalies in 233 test result(s)

rng=RNG_stdin64, seed=0x72e95cf7
length= 64 gigabytes (2^36 bytes), time= 1124 seconds
no anomalies in 244 test result(s)

rng=RNG_stdin64, seed=0x72e95cf7
length= 128 gigabytes (2^37 bytes), time= 2193 seconds
Test Name                         Raw       Processed     Evaluation
Gap-16:B                          R=  +4.1  p =  1.9e-3   unusual
[Low16/64]FPF-14+6/16:all         R=  +5.3  p =  1.7e-4   unusual
...and 253 test result(s) without anomalies

rng=RNG_stdin64, seed=0x72e95cf7
length= 256 gigabytes (2^38 bytes), time= 4239 seconds
Test Name                         Raw       Processed     Evaluation
[Low16/64]FPF-14+6/16:all         R=  +6.4  p =  1.6e-5   mildly suspicious
[Low16/64]FPF-14+6/16:all2        R=  +8.9  p =  2.1e-5   mildly suspicious
...and 263 test result(s) without anomalies

rng=RNG_stdin64, seed=0x72e95cf7
length= 512 gigabytes (2^39 bytes), time= 8493 seconds
Test Name                         Raw       Processed     Evaluation
[Low16/64]FPF-14+6/16:(3,14-0)    R= +11.1  p =  7.2e-10  very suspicious
[Low16/64]FPF-14+6/16:(4,14-0)    R=  +9.0  p =  6.6e-8   suspicious
[Low16/64]FPF-14+6/16:(5,14-0)    R=  +6.9  p =  5.4e-6   unusual
[Low16/64]FPF-14+6/16:all         R= +10.8  p =  1.3e-9    VERY SUSPICIOUS
[Low16/64]FPF-14+6/16:all2        R= +38.1  p =  9.0e-19    FAIL !
...and 271 test result(s) without anomalies
``````

One thing you can see from these results is that the time it takes a generator to fail can vary significantly. The first failed under two minutes, whereas the second took 2 hours, 22 minutes to fail. You also get to see the way things fail, with problems building over time and becoming more obvious as we take more data. One nice thing about PractRand is that unless you tell it to keep going regardless, it stops the moment the generator shows serious failures. In contrast, TestU01 waits to complete the test battery.

One other nice thing about PractRand is that all the tests are being applied at once (sharing the same PRNG output). In contrast, TestU01 runs each test one after the other. In other words, PractRand makes better use of the (purportedly) random data it receives.

In summary, PractRand is a great complement to TestU01. It doesn't have as many statistical tests, but the ones it does have are good ones. It gives you results sooner, and it can test more of the output of a PRNG.

### Testing PCG

Here are the results of testing `pcg64`.

``````linux\$ ./pcg64 | ./RNG_test stdin64
RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0x78041158
test set = normal, folding = standard (64 bit)

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

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

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

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

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

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

rng=RNG_stdin64, seed=0x78041158
length= 8 gigabytes (2^33 bytes), time= 128 seconds
Test Name                         Raw       Processed     Evaluation
[Low4/64]BCFN(2+1,13-1,T)         R=  -7.6  p =1-5.7e-4   unusual
...and 211 test result(s) without anomalies

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

rng=RNG_stdin64, seed=0x78041158
length= 32 gigabytes (2^35 bytes), time= 504 seconds
no anomalies in 233 test result(s)

rng=RNG_stdin64, seed=0x78041158
length= 64 gigabytes (2^36 bytes), time= 998 seconds
no anomalies in 244 test result(s)

rng=RNG_stdin64, seed=0x78041158
length= 128 gigabytes (2^37 bytes), time= 1989 seconds
no anomalies in 255 test result(s)

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

rng=RNG_stdin64, seed=0x78041158
length= 512 gigabytes (2^39 bytes), time= 7932 seconds
no anomalies in 276 test result(s)

rng=RNG_stdin64, seed=0x78041158
length= 1 terabyte (2^40 bytes), time= 16853 seconds
no anomalies in 287 test result(s)

rng=RNG_stdin64, seed=0x78041158
length= 2 terabytes (2^41 bytes), time= 37027 seconds
no anomalies in 297 test result(s)

rng=RNG_stdin64, seed=0x78041158
length= 4 terabytes (2^42 bytes), time= 75378 seconds
no anomalies in 308 test result(s)

rng=RNG_stdin64, seed=0x78041158
length= 8 terabytes (2^43 bytes), time= 147024 seconds
no anomalies in 319 test result(s)

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

rng=RNG_stdin64, seed=0x78041158
length= 32 terabytes (2^45 bytes), time= 563979 seconds
no anomalies in 339 test result(s)
``````

This is exactly the kind of result we might hope for. It takes about a week to run, but in the end completes with no problems. As we would expect, during the test there was a brief moment one of the test results looked unusual but as testing continued it proved to be nothing.

It's a similar story for `pcg64_fast`. In the interest of not filling your screen with junk, I'll switch to abbreviating the rest of the results to show just the beginnings and the ends of the tests.

``````linux\$ ./pcg64_fast | ./RNG_test stdin64
RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0xf24baca7
test set = normal, folding = standard (64 bit)

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

[...]

rng=RNG_stdin64, seed=0xf24baca7
length= 8 terabytes (2^43 bytes), time= 132005 seconds
no anomalies in 319 test result(s)

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

rng=RNG_stdin64, seed=0xf24baca7
length= 32 terabytes (2^45 bytes), time= 526487 seconds
no anomalies in 339 test result(s)
``````

Of course, `pcg64` and `pcg64_fast` have large periods (2128 and 2126, respectively) and large state spaces (2255 and 2127, respectively). 32 TB of output seems like a lot, but these are 64-bit generators outputting 8 bytes at a time, so we've only used 242 numbers from each generator. We haven't even reached the square root of the period; we're closer to the cube root. In my opinion, any generator with 128 bits of state (or more) that fails statistical tests must have some serious flaws. More on that another time.

A greater challenge is to test PCG's smaller generators that produce 32-bit output. Because they only produce four bytes of output, 32 TB represents 243 outputs. `pcg32` and `pcg32_fast` have periods of 264 and 262 and state spaces of 2127 and 263, respectively. Some older papers on random number generation suggest that you should never use more numbers from a generator than the square root of its period, otherwise statistical problems may occur. Those comments date back to an earlier era of generation when generators were lower quality, but I will admit that I had a moment of doubt. Was I wrong to have waited so long to test with PractRand? Would it push these generators past their limits? In theory, based on my prior headroom-based pronouncements with TestU01, no, but what about in practice? (TheorRand vs PractRand!) Let's see...

``````linux\$ ./pcg32 | ./RNG_test stdin32
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0x16692278
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0x16692278
length= 128 megabytes (2^27 bytes), time= 2.3 seconds
no anomalies in 117 test result(s)

[...]

rng=RNG_stdin32, seed=0x16692278
length= 8 terabytes (2^43 bytes), time= 130996 seconds
no anomalies in 244 test result(s)

rng=RNG_stdin32, seed=0x16692278
length= 16 terabytes (2^44 bytes), time= 260545 seconds
no anomalies in 252 test result(s)

rng=RNG_stdin32, seed=0x16692278
length= 32 terabytes (2^45 bytes), time= 519966 seconds
no anomalies in 260 test result(s)
``````
``````linux\$ ./pcg32_fast | ./RNG_test stdin32
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0x3d5f2c7e
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0x3d5f2c7e
length= 128 megabytes (2^27 bytes), time= 2.3 seconds
no anomalies in 117 test result(s)

[...]

rng=RNG_stdin32, seed=0x3d5f2c7e
length= 8 terabytes (2^43 bytes), time= 131096 seconds
no anomalies in 244 test result(s)

rng=RNG_stdin32, seed=0x3d5f2c7e
length= 16 terabytes (2^44 bytes), time= 261300 seconds
no anomalies in 252 test result(s)

rng=RNG_stdin32, seed=0x3d5f2c7e
length= 32 terabytes (2^45 bytes), time= 518888 seconds
no anomalies in 260 test result(s)
``````

One interesting thing to note here is that `pcg32_fast` doesn't seem to be significantly faster than `pcg32`. Most of the time is due to PractRand itself, and the small inefficiency of sending numbers over a Unix pipe, not the random number generation process itself. In other contexts, `pcg32_fast` can be faster.

I could have stopped there, but PractRand provides the option to apply more variations of its tests and try much harder to find flaws. These extended tests make PractRand run more slowly and aren't enabled by default, but it seemed worthwhile to really hammer on `pcg32_fast` as the most vulnerable generator of the ones I recommend for general-purpose use.

``````linux\$ ./pcg32_fast | time ./RNG_test stdin32 -te 1 -tf 2
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0xb5f0bbc4
test set = expanded, folding = extra

rng=RNG_stdin32, seed=0xb5f0bbc4
length= 32 megabytes (2^25 bytes), time= 2.3 seconds
no anomalies in 796 test result(s)

[...]

rng=RNG_stdin32, seed=0xb5f0bbc4
length= 2 terabytes (2^41 bytes), time= 153323 seconds
no anomalies in 1723 test result(s)

rng=RNG_stdin32, seed=0xb5f0bbc4
length= 4 terabytes (2^42 bytes), time= 282780 seconds
no anomalies in 1770 test result(s)

rng=RNG_stdin32, seed=0xb5f0bbc4
length= 8 terabytes (2^43 bytes), time= 539058 seconds
no anomalies in 1816 test result(s)

rng=RNG_stdin32, seed=0xb5f0bbc4
length= 16 terabytes (2^44 bytes), time= 1064442 seconds
no anomalies in 1859 test result(s)

rng=RNG_stdin32, seed=0xb5f0bbc4
length= 32 terabytes (2^45 bytes), time= 2178649 seconds
no anomalies in 1901 test result(s)

./RNG_test stdin32 -te 1 -tf 2  2170392.00s user 9792.10s system 100% cpu 605:11:07.57 total
linux\$
``````

These extended-test results, which represent more than twenty-five days of continuous testing, reveal no problems up to 32 TB (the standard stopping point for PractRand).

#### Making PCG Fail

One of my key arguments about testing is that it isn't enough to proudly say “my generator passes statistical tests” (especially if it has a large period or state space). Instead we should squeeze it down smaller and smaller until it fails.

So, this time we'll test `pcg_engines::setseq_xsh_rr_32_16` and `pcg_engines::mcg_xsh_rs_32_16`, which are half-size versions of `pcg32` and `pcg32_fast`. Their periods are 232 and 230, respectively, and they only produce 16-bit outputs (2 bytes), so it would be utterly unrealistic to expect them to generate 32 TB of data. They must fail. The question is, when? Let's find out!

We'll run PractRand so that it starts telling is about what it is doing a little sooner so we can enjoy some successes before we fail.

``````linux\$ ./pcg_setseq_xsh_rr_32_16  | ./RNG_test stdin16 -tlmin 16
RNG_test using PractRand version 0.93
RNG = RNG_stdin16, seed = 0xe7dc4836
test set = normal, folding = standard (16 bit)

rng=RNG_stdin16, seed=0xe7dc4836
length= 64 kilobytes (2^16 bytes), time= 0.1 seconds
no anomalies in 39 test result(s)

rng=RNG_stdin16, seed=0xe7dc4836
length= 128 kilobytes (2^17 bytes), time= 0.7 seconds
no anomalies in 43 test result(s)

rng=RNG_stdin16, seed=0xe7dc4836
length= 256 kilobytes (2^18 bytes), time= 1.2 seconds
no anomalies in 50 test result(s)

rng=RNG_stdin16, seed=0xe7dc4836
length= 512 kilobytes (2^19 bytes), time= 1.7 seconds
no anomalies in 56 test result(s)

rng=RNG_stdin16, seed=0xe7dc4836
length= 1 megabyte (2^20 bytes), time= 2.3 seconds
no anomalies in 64 test result(s)

rng=RNG_stdin16, seed=0xe7dc4836
length= 2 megabytes (2^21 bytes), time= 2.8 seconds
Test Name                         Raw       Processed     Evaluation
[Low4/16]DC6-9x1Bytes-1           R=  +5.7  p =  5.3e-3   unusual
...and 71 test result(s) without anomalies

rng=RNG_stdin16, seed=0xe7dc4836
length= 4 megabytes (2^22 bytes), time= 3.4 seconds
no anomalies in 79 test result(s)

rng=RNG_stdin16, seed=0xe7dc4836
length= 8 megabytes (2^23 bytes), time= 4.0 seconds
no anomalies in 87 test result(s)

rng=RNG_stdin16, seed=0xe7dc4836
length= 16 megabytes (2^24 bytes), time= 4.6 seconds
no anomalies in 95 test result(s)

rng=RNG_stdin16, seed=0xe7dc4836
length= 32 megabytes (2^25 bytes), time= 5.4 seconds
no anomalies in 103 test result(s)

rng=RNG_stdin16, seed=0xe7dc4836
length= 64 megabytes (2^26 bytes), time= 6.6 seconds
no anomalies in 111 test result(s)

rng=RNG_stdin16, seed=0xe7dc4836
length= 128 megabytes (2^27 bytes), time= 8.7 seconds
Test Name                         Raw       Processed     Evaluation
FPF-14+6/16:all                   R=  -5.3  p =1-1.0e-4   mildly suspicious
...and 118 test result(s) without anomalies

rng=RNG_stdin16, seed=0xe7dc4836
length= 256 megabytes (2^28 bytes), time= 12.4 seconds
Test Name                         Raw       Processed     Evaluation
FPF-14+6/16:all                   R=  -6.4  p =1-7.5e-6   suspicious
...and 126 test result(s) without anomalies

rng=RNG_stdin16, seed=0xe7dc4836
length= 512 megabytes (2^29 bytes), time= 19.0 seconds
Test Name                         Raw       Processed     Evaluation
FPF-14+6/16:(0,14-0)              R=  -9.3  p =1-2.7e-8   very suspicious
FPF-14+6/16:(1,14-0)              R=  -8.5  p =1-1.6e-7   suspicious
FPF-14+6/16:all                   R= -11.5  p =1-7.5e-11   VERY SUSPICIOUS
FPF-14+6/16:all2                  R= +31.0  p =  7.9e-14    FAIL
...and 131 test result(s) without anomalies
``````

So, for `pcg_engines::pcg_setseq_xsh_rr_32_16`, we begin to see intimations of problems at 227 bytes (i.e., 226 16-bit outputs) and a clear fail at 229 bytes (i.e., 228 16-bit outputs). If we extrapolate from that result, `pcg32` might start to show issues sometime around 252 outputs (i.e., 254 bytes; 4 petabytes), and would probably have failed by the time we reach 256 outputs (258 bytes; 256 petabytes). In other words, we can estimate that pcg32 will fail PractRand if increase the test that took a week to complete by a factor somewhere between 512 and 8192. In other words, we might see issues with `pcg32` after 10 years of testing, and we can be pretty sure that if we test for 150 years, it'll have failed by then.

I should also point out that any extrapolation from behavior at small sizes is going to be imperfect. The only sure way to find out whether the full size `pcg32` generator takes a thousand years to fail, or somehow fails unexpectedly after just a few of months, would be actually run tests that might take years to complete. What these small-scale tests provide is a back-of-the-envelope way to make an informed guess about whether testing beyond 32TB is worthwhile. (The headroom analysis in the PCG paper is a little more rigorous than the quite simple test we've done here, but that too is necessarily extrapolatory.)

Now let's move on to the tiny sibling of `pcg32_fast`. We should expect it to do worse, and it does.

``````linux\$ ./pcg_mcg_xsh_rs_32_16 | ./RNG_test stdin16 -tlmin 16
seeding with 0xdd44ecf0
RNG_test using PractRand version 0.93
RNG = RNG_stdin16, seed = 0x1aac2a7b
test set = normal, folding = standard (16 bit)

rng=RNG_stdin16, seed=0x1aac2a7b
length= 64 kilobytes (2^16 bytes), time= 0.1 seconds
no anomalies in 39 test result(s)

rng=RNG_stdin16, seed=0x1aac2a7b
length= 128 kilobytes (2^17 bytes), time= 0.7 seconds
no anomalies in 43 test result(s)

rng=RNG_stdin16, seed=0x1aac2a7b
length= 256 kilobytes (2^18 bytes), time= 1.2 seconds
no anomalies in 50 test result(s)

rng=RNG_stdin16, seed=0x1aac2a7b
length= 512 kilobytes (2^19 bytes), time= 1.8 seconds
no anomalies in 56 test result(s)

rng=RNG_stdin16, seed=0x1aac2a7b
length= 1 megabyte (2^20 bytes), time= 2.3 seconds
no anomalies in 64 test result(s)

rng=RNG_stdin16, seed=0x1aac2a7b
length= 2 megabytes (2^21 bytes), time= 2.8 seconds
no anomalies in 72 test result(s)

rng=RNG_stdin16, seed=0x1aac2a7b
length= 4 megabytes (2^22 bytes), time= 3.4 seconds
no anomalies in 79 test result(s)

rng=RNG_stdin16, seed=0x1aac2a7b
length= 8 megabytes (2^23 bytes), time= 4.0 seconds
no anomalies in 87 test result(s)

rng=RNG_stdin16, seed=0x1aac2a7b
length= 16 megabytes (2^24 bytes), time= 4.6 seconds
Test Name                         Raw       Processed     Evaluation
Gap-16:A                          R=  +7.3  p =  2.5e-5   suspicious
...and 94 test result(s) without anomalies

rng=RNG_stdin16, seed=0x1aac2a7b
length= 32 megabytes (2^25 bytes), time= 5.4 seconds
Test Name                         Raw       Processed     Evaluation
Gap-16:A                          R=  +9.1  p =  5.9e-7   very suspicious
...and 102 test result(s) without anomalies

rng=RNG_stdin16, seed=0x1aac2a7b
length= 64 megabytes (2^26 bytes), time= 6.5 seconds
Test Name                         Raw       Processed     Evaluation
Gap-16:A                          R= +17.4  p =  1.3e-14    FAIL !
Gap-16:B                          R=  +9.5  p =  3.4e-8   very suspicious
FPF-14+6/16:all                   R=  -6.3  p =1-9.0e-6   suspicious
...and 108 test result(s) without anomalies
``````

Here we see PractRand becoming suspicious at 224 bytes (i.e., 223 outputs) and failing at 226 (i.e., 225 outputs). This generator has a period of 230, whereas `pcg32_fast` has a period of 262. Thus the equivalent points for `pcg32_fast` would be 2(23/30)×62 and 2(25/30)×62, or somewhere between 0.72 petabytes of output and 12.7 petabytes, or somewhere between 23 weeks and 7.8 years of testing.

### Comparison with SplitMix

To set these results into context, it helps to compare them with another PRNG. Popular choices that Internet folks might want to see are comparisons with SplitMix and Xoroshiro128+. XoroShiro isn't a good choice for comparison because it is already known to fail some of PractRand's statistical tests, as acknowledged by its authors in its source code, although the extent of the issues are larger, so that comparison will have to wait for another day (coming soon!).

In some ways I quite like SplitMix because it has some similar ideas to PCG in that it avoids having a trivial output function, but it does have a trivial state transition function. If we test a full-sized version of SplitMix, we find it passes PractRand.

``````linux\$ ./splitmix | ./RNG_test stdin64
RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0xbb88093
test set = normal, folding = standard (64 bit)

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

[...]

rng=RNG_stdin64, seed=0xbb88093
length= 8 terabytes (2^43 bytes), time= 132138 seconds
no anomalies in 319 test result(s)

rng=RNG_stdin64, seed=0xbb88093
length= 16 terabytes (2^44 bytes), time= 265163 seconds
Test Name                         Raw       Processed     Evaluation
[Low1/64]FPF-14+6/16:all          R=  +5.4  p =  1.6e-4   unusual
...and 328 test result(s) without anomalies

rng=RNG_stdin64, seed=0xbb88093
length= 32 terabytes (2^45 bytes), time= 530227 seconds
Test Name                         Raw       Processed     Evaluation
[Low4/64]BCFN(2+2,13-0,T)         R=  +7.6  p =  1.4e-3   unusual
...and 338 test result(s) without anomalies
``````

Notice that SplitMix is not (necessarily) starting to fail here. We already know that something statistically “unusual” must be expected to happen occasionally. The fact that different tests fail means that we're not (yet) seeing any systemic breakdown.

So we could say, SplitMix passes, PCG passes, all is good. But let's instead test a cut-down version of SplitMix equivalent to the cut-down versions of pcg32 we tested earlier. For a fair comparison, we'll test its 16-bit output function.

``````linux\$ ./splitmix32 | ./RNG_test stdin16 -tlmin 16
RNG_test using PractRand version 0.93
RNG = RNG_stdin16, seed = 0xdfafcc2c
test set = normal, folding = standard (16 bit)

rng=RNG_stdin16, seed=0xdfafcc2c
length= 64 kilobytes (2^16 bytes), time= 0.1 seconds
no anomalies in 39 test result(s)

rng=RNG_stdin16, seed=0xdfafcc2c
length= 128 kilobytes (2^17 bytes), time= 0.7 seconds
no anomalies in 43 test result(s)

rng=RNG_stdin16, seed=0xdfafcc2c
length= 256 kilobytes (2^18 bytes), time= 1.2 seconds
no anomalies in 50 test result(s)

rng=RNG_stdin16, seed=0xdfafcc2c
length= 512 kilobytes (2^19 bytes), time= 1.8 seconds
no anomalies in 56 test result(s)

rng=RNG_stdin16, seed=0xdfafcc2c
length= 1 megabyte (2^20 bytes), time= 2.3 seconds
Test Name                         Raw       Processed     Evaluation
[Low4/16]Gap-16:B                 R=  +4.1  p =  3.0e-3   unusual
...and 63 test result(s) without anomalies

rng=RNG_stdin16, seed=0xdfafcc2c
length= 2 megabytes (2^21 bytes), time= 2.8 seconds
Test Name                         Raw       Processed     Evaluation
Gap-16:A                          R=  +5.4  p =  4.9e-4   unusual
...and 71 test result(s) without anomalies

rng=RNG_stdin16, seed=0xdfafcc2c
length= 4 megabytes (2^22 bytes), time= 3.4 seconds
Test Name                         Raw       Processed     Evaluation
Gap-16:A                          R=  +6.6  p =  7.3e-5   mildly suspicious
...and 78 test result(s) without anomalies

rng=RNG_stdin16, seed=0xdfafcc2c
length= 8 megabytes (2^23 bytes), time= 4.0 seconds
Test Name                         Raw       Processed     Evaluation
Gap-16:A                          R=  +8.4  p =  1.6e-6   very suspicious
...and 86 test result(s) without anomalies

rng=RNG_stdin16, seed=0xdfafcc2c
length= 16 megabytes (2^24 bytes), time= 4.6 seconds
Test Name                         Raw       Processed     Evaluation
Gap-16:A                          R= +16.8  p =  7.3e-13    FAIL
...and 94 test result(s) without anomalies
``````

Here, we can see SplitMix32 showing a clear tell by 222 bytes (221 outputs) and failing by 224 bytes (223 outputs). That result is clearly much worse than `pcg32_fast`, which is the weakest PCG generator I would recommend for general purpose use.

If performance at small sizes really is a proxy to performance at larger sizes, the full-size SplitMix is actually very close to failing a regular run of PractRand. I've set a longer test in motion and we'll see what happens. If it does fail, it validates the approach of testing at small sizes. On the other hand, if it doesn't fail, it shows that the small-size results may sometimes be too pessimistic.

Regardless, it seems that in a PractRand statistical quality contest, `pcg32` and `pcg32_fast` beat SplitMix (and Xoroshiro128+, because it doesn't pass PractRand's tests to begin with).

### Conclusion

Results from PractRand do indeed validate the statistical quality claims I've made about the PCG family. Yay!