Introduction
This page reviews Melissa O'Neill's PCG generators. It is structured as follows: first, we identify the generators with major statistical flaw. Once those are out of the picture, we examine some claims made by Melissa O'Neill on the remaining PCG generators, and provide simple counterexamples for each claim. In the end, we show simple generators based on congruential arithmetic that are faster and have better statistical properties of the only remaining 64-bit PCG generators.
The conclusion is that there is no reason to use PCG generators: for those without statistical flaws, there is always a better choice.
Statistical flaws
Generator with “ext” in the name
Generator with a large state space are useful because they generate many distinct and uncorrelated sequences. In theory, all nonoverlapping subsequences should look random, so if you take R and R' initialized in a different state and interleave their output (first output from R, then first output from R', then second output from R, etc.) the resulting sequence should still look random.
But nothing is really random. So what you do is correlation testing: you take R. Then you take an exact copy of R, R', and you flip exactly one bit of the state. Then you interleave as above, and examine the output (usually using some test suite, you can choose the one you prefer).
In theory the interleaved output should immediately look random, but that's very
difficult to obtain, because it takes time for the flipped bit to
influence all the state. So you have to throw away some output from
R, R' before they decorrelate.
For example, xoroshiro128+ decorrelates after
a couple of dozens iterations. The Mersenne Twister (19937 bits of state) after millions of
iterations. CMWC4096, the “Mother-of-all” PRNG by Marsaglia, needs
more than 10,000,000 iterations. That is, you have to discard 10,000,000 values from
R and R' before you see a random interleaved stream.
LCG generators can only be as large as the largest multiplications you can perform. Melissa O'Neill devised a new type of generators (the ones with “ext” in their name) which, mysteriously, overcome this limit.
So let us try to see how much does it take for an “ext” PCG generator to decorrelate. I wrote a C++ program that does a correlation test for you: it creates two “ext” PCG generators, flips a bit of the “ext” state, and emits the output interleaved. It takes a parameter that specifies the number of iterations to perform before emitting the interleaved stream, so we can measure whether, for example, uncorrelation is faster than with the Mersenne Twister.
This is the result with 1 million discarded outputs:
rng=RNG_stdin64, seed=0x5e3432a3
length= 256 megabytes (2^28 bytes), time= 2.2 seconds
Test Name Raw Processed Evaluation
BCFN(2+0,13-2,T) R=+5218351 p = 0 FAIL !!!!!!!!
BCFN(2+1,13-2,T) R=+3553737 p = 0 FAIL !!!!!!!!
BCFN(2+2,13-3,T) R= +4207 p = 3e-1991 FAIL !!!!!!!!
BCFN(2+3,13-3,T) R=+966.0 p = 4.9e-457 FAIL !!!!!!!
BCFN(2+4,13-3,T) R=+203.5 p = 4.2e-96 FAIL !!!!!
BCFN(2+5,13-4,T) R= +30.7 p = 2.2e-13 FAIL
DC6-9x1Bytes-1 R=+313150 p = 0 FAIL !!!!!!!!
Gap-16:A R=+2924020 p = 0 FAIL !!!!!!!!
Gap-16:B R=+11092511 p = 0 FAIL !!!!!!!!
FPF-14+6/16:(0,14-0) R=+121.6 p = 3.6e-112 FAIL !!!!!
FPF-14+6/16:(1,14-0) R=+125.2 p = 1.8e-115 FAIL !!!!!
FPF-14+6/16:(2,14-0) R=+109.4 p = 7.2e-101 FAIL !!!!!
FPF-14+6/16:(3,14-0) R= +99.7 p = 7.5e-92 FAIL !!!!!
FPF-14+6/16:(4,14-1) R= +72.7 p = 3.4e-64 FAIL !!!!
FPF-14+6/16:(5,14-2) R= +55.4 p = 2.9e-48 FAIL !!!
FPF-14+6/16:(6,14-2) R= +48.4 p = 4.2e-42 FAIL !!!
FPF-14+6/16:(7,14-3) R= +37.3 p = 1.7e-32 FAIL !!!
FPF-14+6/16:(8,14-4) R= +22.5 p = 2.5e-18 FAIL !
FPF-14+6/16:(9,14-5) R= +22.2 p = 3.0e-18 FAIL !
FPF-14+6/16:(10,14-5) R= +18.2 p = 6.2e-15 FAIL
FPF-14+6/16:(13,14-8) R= +8.6 p = 3.0e-6 unusual
FPF-14+6/16:(15,14-9) R= +8.7 p = 8.9e-6 unusual
FPF-14+6/16:all R=+255.7 p = 1.7e-239 FAIL !!!!!!
FPF-14+6/16:all2 R=+14532 p = 4e-5671 FAIL !!!!!!!!
BRank(12):128(4) R= +2501 p~= 3e-1331 FAIL !!!!!!!!
BRank(12):256(4) R= +5257 p~= 1e-2796 FAIL !!!!!!!!
BRank(12):384(1) R= +3963 p~= 4e-1194 FAIL !!!!!!!!
BRank(12):512(2) R= +7614 p~= 4e-2293 FAIL !!!!!!!!
BRank(12):768(1) R= +8096 p~= 2e-2438 FAIL !!!!!!!!
BRank(12):1K(2) R=+15408 p~= 3e-4639 FAIL !!!!!!!!
BRank(12):1536(1) R=+16298 p~= 2e-4907 FAIL !!!!!!!!
BRank(12):2K(1) R=+21895 p~= 3e-6592 FAIL !!!!!!!!
[Low16/64]BCFN(2+0,13-3,T) R=+16181 p = 2e-7658 FAIL !!!!!!!!
[Low16/64]BCFN(2+1,13-3,T) R= +3654 p = 3e-1729 FAIL !!!!!!!!
[Low16/64]BCFN(2+2,13-4,T) R=+903.0 p = 1.8e-394 FAIL !!!!!!!
[Low16/64]BCFN(2+3,13-4,T) R=+118.4 p = 1.1e-51 FAIL !!!!
[Low16/64]BCFN(2+5,13-5,T) R= +13.7 p = 1.5e-5 mildly suspicious
[Low16/64]DC6-9x1Bytes-1 R=+965794 p = 0 FAIL !!!!!!!!
[Low16/64]Gap-16:A R=+838770 p = 0 FAIL !!!!!!!!
[Low16/64]Gap-16:B R=+3576303 p = 0 FAIL !!!!!!!!
[Low16/64]FPF-14+6/16:(0,14-0) R=+122.4 p = 7.1e-113 FAIL !!!!!
[Low16/64]FPF-14+6/16:(1,14-0) R=+127.5 p = 1.3e-117 FAIL !!!!!
[Low16/64]FPF-14+6/16:(2,14-1) R= +85.7 p = 1.0e-75 FAIL !!!!
[Low16/64]FPF-14+6/16:(3,14-2) R= +59.7 p = 5.4e-52 FAIL !!!!
[Low16/64]FPF-14+6/16:(4,14-2) R= +4010 p = 4e-3507 FAIL !!!!!!!!
[Low16/64]FPF-14+6/16:(5,14-3) R= +2834 p = 4e-2484 FAIL !!!!!!!!
[Low16/64]FPF-14+6/16:(6,14-4) R= +2010 p = 2e-1642 FAIL !!!!!!!!
[Low16/64]FPF-14+6/16:(7,14-5) R= +1428 p = 1e-1183 FAIL !!!!!!!!
[Low16/64]FPF-14+6/16:(8,14-5) R= +1714 p = 2e-1421 FAIL !!!!!!!!
[Low16/64]FPF-14+6/16:(9,14-6) R= +1216 p = 2.1e-930 FAIL !!!!!!!
[Low16/64]FPF-14+6/16:(10,14-7) R=+849.5 p = 6.3e-676 FAIL !!!!!!!
[Low16/64]FPF-14+6/16:(11,14-8) R=+584.7 p = 8.6e-421 FAIL !!!!!!!
[Low16/64]FPF-14+6/16:(12,14-8) R=+540.8 p = 3.4e-389 FAIL !!!!!!!
[Low16/64]FPF-14+6/16:(13,14-9) R=+384.8 p = 1.4e-242 FAIL !!!!!!
[Low16/64]FPF-14+6/16:(14,14-10) R=+269.5 p = 6.3e-144 FAIL !!!!!
[Low16/64]FPF-14+6/16:(15,14-11) R=+214.6 p = 2.2e-94 FAIL !!!!!
[Low16/64]FPF-14+6/16:all R= +2608 p = 1e-2447 FAIL !!!!!!!!
[Low16/64]FPF-14+6/16:all2 R=+7572279 p = 0 FAIL !!!!!!!!
[Low16/64]FPF-14+6/16:cross R= +75.0 p = 2.8e-66 FAIL !!!!
[Low16/64]BRank(12):128(4) R= +2501 p~= 3e-1331 FAIL !!!!!!!!
[Low16/64]BRank(12):256(2) R= +3717 p~= 5e-1120 FAIL !!!!!!!!
[Low16/64]BRank(12):384(1) R= +3963 p~= 4e-1194 FAIL !!!!!!!!
[Low16/64]BRank(12):512(2) R= +7599 p~= 1e-2288 FAIL !!!!!!!!
[Low16/64]BRank(12):768(1) R= +8096 p~= 2e-2438 FAIL !!!!!!!!
[Low16/64]BRank(12):1K(1) R=+10873 p~= 3e-3274 FAIL !!!!!!!!
[Low4/64]BCFN(2+0,13-5,T) R= +4244 p = 1e-1661 FAIL !!!!!!!!
[Low4/64]BCFN(2+1,13-5,T) R=+597.8 p = 3.4e-234 FAIL !!!!!!
[Low4/64]BCFN(2+2,13-5,T) R= +13.7 p = 1.5e-5 suspicious
[Low4/64]BCFN(2+3,13-5,T) R= +61.2 p = 3.7e-24 FAIL !!
[Low4/64]BCFN(2+4,13-6,T) R= +41.7 p = 1.0e-14 FAIL
[Low4/64]BCFN(2+5,13-6,T) R= +14.0 p = 3.0e-5 unusual
[Low4/64]DC6-9x1Bytes-1 R=+115116 p = 0 FAIL !!!!!!!!
[Low4/64]Gap-16:A R=+247785 p = 0 FAIL !!!!!!!!
[Low4/64]Gap-16:B R=+1522079 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(0,14-1) R=+363333 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(1,14-2) R=+256697 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(2,14-2) R=+148798 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(3,14-3) R=+105460 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(8,14-7) R=+111527 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(9,14-8) R=+78894 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(10,14-8) R=+39682 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(11,14-9) R=+28140 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:all R=+502730 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:all2 R=+68561676162 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:cross R=+525391 p = 0 FAIL !!!!!!!!
[Low4/64]BRank(12):128(4) R= +2501 p~= 3e-1331 FAIL !!!!!!!!
[Low4/64]BRank(12):256(2) R= +3717 p~= 5e-1120 FAIL !!!!!!!!
[Low4/64]BRank(12):384(1) R= +4028 p~= 1e-1213 FAIL !!!!!!!!
[Low4/64]BRank(12):512(2) R= +7599 p~= 1e-2288 FAIL !!!!!!!!
[Low4/64]BRank(12):768(1) R= +8096 p~= 2e-2438 FAIL !!!!!!!!
[Low1/64]BCFN(2+0,13-6,T) R= +76.9 p = 8.8e-27 FAIL !!
[Low1/64]BCFN(2+1,13-6,T) R=+375.0 p = 7.6e-129 FAIL !!!!!
[Low1/64]BCFN(2+2,13-6,T) R=+167.7 p = 7.4e-58 FAIL !!!!
[Low1/64]BCFN(2+3,13-6,T) R= +42.5 p = 5.5e-15 FAIL !
[Low1/64]BCFN(2+4,13-7,T) R= +16.2 p = 1.6e-5 mildly suspicious
[Low1/64]DC6-9x1Bytes-1 R=+36425 p = 0 FAIL !!!!!!!!
[Low1/64]Gap-16:A R=+88655 p = 0 FAIL !!!!!!!!
[Low1/64]Gap-16:B R=+526412 p = 0 FAIL !!!!!!!!
[Low1/64]FPF-14+6/16:(0,14-2) R=+123481 p = 0 FAIL !!!!!!!!
[Low1/64]FPF-14+6/16:(2,14-4) R=+100738 p = 0 FAIL !!!!!!!!
[Low1/64]FPF-14+6/16:(4,14-5) R=+71077 p = 0 FAIL !!!!!!!!
[Low1/64]FPF-14+6/16:(6,14-7) R=+55336 p = 0 FAIL !!!!!!!!
[Low1/64]FPF-14+6/16:(8,14-8) R=+27843 p = 0 FAIL !!!!!!!!
[Low1/64]FPF-14+6/16:(10,14-10) R=+16804 p = 2e-8940 FAIL !!!!!!!!
[Low1/64]FPF-14+6/16:(11,14-11) R= +2225 p = 2.0e-970 FAIL !!!!!!!
[Low1/64]FPF-14+6/16:(12,14-11) R=+14981 p = 2e-6530 FAIL !!!!!!!!
[Low1/64]FPF-14+6/16:all R=+215351 p = 0 FAIL !!!!!!!!
[Low1/64]FPF-14+6/16:all2 R=+10216812555 p = 0 FAIL !!!!!!!!
[Low1/64]FPF-14+6/16:cross R=+521082 p = 0 FAIL !!!!!!!!
[Low1/64]BRank(12):128(2) R= +1769 p~= 1.8e-533 FAIL !!!!!!!
[Low1/64]BRank(12):256(2) R= +3717 p~= 5e-1120 FAIL !!!!!!!!
[Low1/64]BRank(12):384(1) R= +4006 p~= 5e-1207 FAIL !!!!!!!!
[Low1/64]BRank(12):512(1) R= +5362 p~= 2e-1615 FAIL !!!!!!!!
...and 37 test result(s) without anomalies
This does not look good. And with 1 billion discarded outputs the result is the same (try yourself). What's happening?
The problem is that “ext” PCG generators never decorrelate. Ever (“never” here means “not before the thermodynamic death of the universe”). There is no state mix. Nobody has ever thought of designing a PRNG in such a flawed way.
The trick used by Melissa O'Neill to make people believe she could have high-quality, large-state generators using LCGs consists, in practice, in xoring the output of a small (at most 128 bits of state) PCG generator with a large array. The array in theory changes, and waiting enough (much beyond the thermodynamical death of the universe) you will see it pass all states, but in practice the array never changes. This is why we cannot decorrelate: the output of R and R' is essentially the same, no matter how much you look for uncorrelated sequences.
Said otherwise, the whole sequence of the generator is made by an enormous number of strongly correlated, very short sequences. And this makes the correlation tests fail.
You can see this easily by uncommenting the printf() calls in the code and commenting the fwrite() calls.
After a billion iterations, we obtain
d355d4a2d198b55d
d355d4a2d198b55d
943c19906dee85e4
943c19906dee85e4
0d4a2d01a24d80ae
0d4a2d01a24d80ae
12d5e10f7a626cbd
12d5e10f7a626cbd
15aedbb162473964
15aedbb162473964
a9700b058d3d2619
a9700b058d3d2619
6a5ed46c771c73d2
6a5ed46c771c73d2
426ca5c99a4980d1
426ca5c99a4980d1
b793262f0f13b965
b793262f0f13b965
be6724c0f4789316
be6724c0f4789316
2ee214efcc33da12
2ee214efcc33da12
38f221757282c60e
38f221757282c60e
e03e6c696146fc81
e03e6c696146fc81
16b1ec780e875744
8f9efedf6709a41e
fe8dbdbbf39eddd3
fe8dbdbbf39eddd3
047ff5f2784f6e08
047ff5f2784f6e08
6d91e2bebd70954a
6d91e2bebd70954a
Almost all outputs are duplicate: the two generators are not decorrelating. If you look carefully, you'll find two values that are not duplicate. This is all the decorrelation we get after a billion iterations, and it will not improve (not significantly before the thermodynamical death of the universe).
Of course, the same test on the very small number of bits of the base generator should work without problems (but read below): nonetheless, the test fails for the large majority of bits of state; and the larger the state space, the worst the percentage of failing bits. No modern generator will fail this test on a majority of bits; in fact, good generators do not fail it on any bit. You just might have to discard a small amount of output values.
Wrap-up: do not use PCG generators with “ext” in the name.
Generators with multiple sequences
Melissa O'Neill claims that a strong point of PCG generators is the possibility of generating multiple independent streams by changing the additive constant of the underlying LCG generator. This fact is stated without any proof, and indeed it is entirely false. You can definitely generate multiple streams, but they might end up being extremely correlated. This is known at least since Knuth's description of LCGs in TAoCP (like, half a century?) because it is possible to derive easily the sequence for a constant given the sequence for another constant. That is, the sequences are strongly correlated, and the minimal scrambling performed by PCG generator is absolutely insufficient to hide this correlation.
To check that this actually happens, I put together a small C program which creates two PCG generators with seemingly random initial states
0x7C112EEA363433CFB3AA1BA7C748A9B9
0x83EED115C9CBCC304C55E45838B75647
and seemingly random increments
0x3E0897751B1A19E7D9D50DD3E3A454DC
0x41F7688AE4E5E618262AF22C1C5BAB23
Following Melissa O'Neill claims, if we interleave the output of these two generators we should see a random stream. But if you pipe the output of the program into PractRand this is what you will see:
rng=RNG_stdin64, seed=0x66b6c6c9
length= 256 megabytes (2^28 bytes), time= 2.9 seconds
Test Name Raw Processed Evaluation
BCFN(2+0,13-2,T) R=+401986 p = 0 FAIL !!!!!!!!
BCFN(2+1,13-2,T) R=+188.0 p = 1.1e-95 FAIL !!!!!
DC6-9x1Bytes-1 R= +7342 p = 1e-3850 FAIL !!!!!!!!
[Low16/64]BCFN(2+0,13-3,T) R= +3288 p = 6e-1556 FAIL !!!!!!!!
[Low16/64]BCFN(2+1,13-3,T) R=+841.7 p = 3.6e-398 FAIL !!!!!!!
[Low16/64]BCFN(2+2,13-4,T) R=+266.1 p = 3.2e-116 FAIL !!!!!
[Low16/64]BCFN(2+3,13-4,T) R= +61.8 p = 6.3e-27 FAIL !!
[Low16/64]BCFN(2+4,13-5,T) R= +14.4 p = 8.1e-6 mildly suspicious
[Low16/64]DC6-9x1Bytes-1 R=+30611 p = 0 FAIL !!!!!!!!
[Low16/64]FPF-14+6/16:(4,14-2) R=+162.5 p = 6.8e-142 FAIL !!!!!
[Low16/64]FPF-14+6/16:(5,14-3) R= +69.8 p = 6.7e-61 FAIL !!!!
[Low16/64]FPF-14+6/16:(6,14-4) R=+112.0 p = 1.9e-91 FAIL !!!!!
[Low16/64]FPF-14+6/16:(7,14-5) R= +43.2 p = 1.1e-35 FAIL !!!
[Low16/64]FPF-14+6/16:(8,14-5) R=+106.9 p = 1.7e-88 FAIL !!!!
[Low16/64]FPF-14+6/16:(9,14-6) R=+118.2 p = 1.6e-90 FAIL !!!!!
[Low16/64]FPF-14+6/16:(10,14-7) R= +78.3 p = 3.9e-62 FAIL !!!!
[Low16/64]FPF-14+6/16:(11,14-8) R= +82.3 p = 3.0e-59 FAIL !!!!
[Low16/64]FPF-14+6/16:(12,14-8) R= +81.6 p = 9.5e-59 FAIL !!!!
[Low16/64]FPF-14+6/16:(13,14-9) R= +57.3 p = 2.3e-36 FAIL !!!
[Low16/64]FPF-14+6/16:(14,14-10) R= +50.0 p = 3.6e-27 FAIL !!
[Low16/64]FPF-14+6/16:(15,14-11) R= +21.8 p = 2.4e-10 very suspicious
[Low16/64]FPF-14+6/16:all R=+106.3 p = 3.1e-99 FAIL !!!!!
[Low16/64]FPF-14+6/16:all2 R=+17519 p = 3e-6345 FAIL !!!!!!!!
[Low16/64]FPF-14+6/16:cross R= +18.0 p = 3.9e-16 FAIL !
[Low4/64]BCFN(2+0,13-5,T) R=+130.0 p = 4.5e-51 FAIL !!!!
[Low4/64]BCFN(2+1,13-5,T) R= +40.9 p = 3.4e-16 FAIL !
[Low4/64]BCFN(2+2,13-5,T) R= +9.6 p = 6.3e-4 unusual
[Low4/64]DC6-9x1Bytes-1 R= +3254 p = 2e-1883 FAIL !!!!!!!!
[Low4/64]Gap-16:A R=+249.7 p = 2.0e-196 FAIL !!!!!!
[Low4/64]Gap-16:B R= +1533 p = 1e-1385 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(0,14-1) R= +3544 p = 1e-3140 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(1,14-2) R= +2511 p = 1e-2195 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(2,14-2) R= +1372 p = 1e-1199 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:(3,14-3) R= +1058 p = 5.1e-927 FAIL !!!!!!!
[Low4/64]FPF-14+6/16:(4,14-4) R=+618.7 p = 1.8e-505 FAIL !!!!!!!
[Low4/64]FPF-14+6/16:(5,14-5) R=+241.6 p = 3.4e-200 FAIL !!!!!!
[Low4/64]FPF-14+6/16:(6,14-5) R=+179.2 p = 2.1e-148 FAIL !!!!!
[Low4/64]FPF-14+6/16:(7,14-6) R=+159.9 p = 1.9e-122 FAIL !!!!!
[Low4/64]FPF-14+6/16:(8,14-7) R=+159.7 p = 6.0e-127 FAIL !!!!!
[Low4/64]FPF-14+6/16:(9,14-8) R=+122.3 p = 5.0e-88 FAIL !!!!
[Low4/64]FPF-14+6/16:(10,14-8) R= +47.9 p = 1.6e-34 FAIL !!!
[Low4/64]FPF-14+6/16:(11,14-9) R= +34.8 p = 3.5e-22 FAIL !!
[Low4/64]FPF-14+6/16:(12,14-10) R= +26.3 p = 1.5e-14 FAIL
[Low4/64]FPF-14+6/16:all R= +4730 p = 6e-4439 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:all2 R=+5302901 p = 0 FAIL !!!!!!!!
[Low4/64]FPF-14+6/16:cross R= +5962 p = 8e-4680 FAIL !!!!!!!!
...and 113 test result(s) without anomalies
In fact, a very large number of different initialization parameters will lead to the same failures. This happens because modulo an additive constant there are just two sequences that can be produced by an LCG of the type used by PCG, no matter which constant you are using. The idea that different constants generate truly different sequences is entirely false.
This is known at least since Durst's 1989 paper: if you have an LCG of the form xn = a xn – 1 + c, and you take any r, then the generator yn = a yn – 1 + c + (a – 1)r satisfies xn = yn – r for all n. It is easy to see by induction starting from x0 = y0 – r, as yn = a yn – 1 + c = a (xn – 1 – r) + c + (a – 1)r = a xn – 1 + c – r = xn – r.
Because of the type of constant used by PCG, called of high potency (it's a good property in general), for every pair of constants c and d such that c – d is divisible by four you can find such an r. This divides the constants in two equivalence classes, and the sequences in each class are basically the same—they differ just by an additive constant. This minimal difference makes the sequences massively correlated, and this correlation passes without difficulty the minimum scrambling of PCG generators; hence the disaster above.
If you want to see this correlation directly, you can try a program that given a state and two “independent stream” initializers, will start two PCG 128-bit generators using the provided initializers: the first generator will start from the provided state, the second generator from the associated state in the correspondence above. The difference between the states of the two generators will always be the same constant, and the program just prints it as the state of both generators advances:
./pcg128diff 0x2360ed051fc65da4 0x4385df649fccf645 0x5851f42d4c957f2d 0x14057b7ef767814f 0xbf58476d1ce4e5b9 0x94d049bb133111eb
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
0xf48e95bc9761ba1d9a9628d3d501146e
Two generators following the same states modulo an additive constant cannot generate “independent streams“. If you modify the program to write the output of the two generators interleaved and pipe the result into PractRand, you will see a cascade of statistical failures as shown above.
Wrap-up: Do not use PCG generators with multiple sequences.
Subsequences within the same generator
It is instructive to look inside a single-sequence 128-bit PCG generator and consider the many possible sequences it can emit starting from different initial states, similarly to what we did with “ext” generators. We already mentioned that the sequence emitted by an LCG when using a certain additive constant can be obtained from the sequence for another additive constant, but in fact much more is true: the output for any additive constant and any initial state can be computed easily knowing the output from state 0 using the additive constant 1.
For prime moduli, nothing particularly bad happens. But if the modulus is not prime, there are consequences, and the worst consequences are for a modulus which is the power of a prime, as in the PCG case (which is why LCGs with moduli of the form 2n, as the ones used in PCG generators, are considered of low quality). Essentially, changing the high bits of the state has no impact on the low bits—forever. And, as in the previous case, this structural defect is passed on to PCG generators.
I put together a small C program
which creates two 128-bit PCG generators. You provide the initial state of the first
generator, and the highest 64 bits of the state of the second generator; the lowest
64 bits will be identical to the first one. Then the program emits the output of
the two PCG generators, interleaved. Let us try with random arguments
0x596d84dfefec2fc7, 0x6b79f81ab9f3e37b and 0x8d7deae980a64ab0
(i.e., the first PCG generator will start from state 0x596d84dfefec2fc76b79f81ab9f3e37b
and the second generator from state 0x8d7deae980a64ab06b79f81ab9f3e37b) and pipe into PractRand:
rng=RNG_stdin64, seed=unknown length= 16 gigabytes (2^34 bytes), time= 411 seconds Test Name Raw Processed Evaluation BCFN(0+0,13-0,T) R= +22.5 p = 1.3e-11 VERY SUSPICIOUS BCFN(0+1,13-0,T) R=+374.9 p = 5.5e-200 FAIL !!!!!! BCFN(0+2,13-0,T) R=+296.4 p = 5.2e-158 FAIL !!!!! DC6-5x4Bytes-1 R= +85.3 p = 1.2e-51 FAIL !!!! ...and 1637 test result(s) without anomalies
In spite of half the bits of the initial state being different, and in spite of having waited billion outputs for the two sequences emitted by the PCG generator to decorrelate, decorrelation does not happen: for every sequence emitted by a PCG generator, there is a very large number of non-overlapping correlated sequences starting from different initial states.
If we change just the highest 32 bits insted of the highest 64 bits the results are so catastrophic to be embarrasing (I removed hundreds of lines):
rng=RNG_stdin64, seed=unknown length= 64 megabytes (2^26 bytes), time= 2.3 seconds Test Name Raw Processed Evaluation BCFN(0+0,13-3,T) R= +6430 p = 2e-3043 FAIL !!!!!!!! BCFN(0+1,13-3,T) R=+15707 p = 3e-7434 FAIL !!!!!!!! BCFN(0+2,13-3,T) R=+10498 p = 1e-4968 FAIL !!!!!!!! ... mod3n(0):(0,9-0) R= +33.9 p = 1.3e-18 FAIL ! DC6-9x1Bytes-1 R=+477.5 p = 6.1e-304 FAIL !!!!!! DC6-6x2Bytes-1 R= +1872 p = 2e-1233 FAIL !!!!!!!! DC6-5x4Bytes-1 R= +1618 p = 1e-1085 FAIL !!!!!!!! Gap-16:A R=+483.3 p = 2.7e-422 FAIL !!!!!!! Gap-16:B R= +1032 p = 1.9e-918 FAIL !!!!!!! [Low1/8]BCFN(0+0,13-5,T) R=+352.1 p = 5.3e-138 FAIL !!!!! [Low1/8]BCFN(0+1,13-5,T) R= +18.4 p = 2.2e-7 suspicious [Low1/8]DC6-9x1Bytes-1 R= +40.6 p = 2.3e-21 FAIL !! [Low1/8]DC6-6x2Bytes-1 R= +81.9 p = 9.3e-50 FAIL !!!! [Low1/8]DC6-5x4Bytes-1 R= +38.3 p = 3.3e-21 FAIL !! [Low1/8]FPF-14+6/64:(0,14-3) R= +19.8 p = 3.7e-17 FAIL [Low1/8]FPF-14+6/64:(1,14-4) R= +12.7 p = 2.7e-10 very suspicious [Low1/8]FPF-14+6/64:(2,14-5) R= +9.4 p = 1.1e-7 mildly suspicious [Low1/8]FPF-14+6/64:(3,14-5) R= +17.1 p = 4.5e-14 FAIL [Low1/8]FPF-14+6/64:(6,14-8) R= +14.0 p = 3.8e-10 very suspicious [Low1/8]FPF-14+6/64:(7,14-8) R= +12.1 p = 9.2e-9 suspicious ... [Low8/64]FPF-14+6/4:(9,14-7) R= +12.8 p = 4.8e-10 very suspicious [Low8/64]FPF-14+6/4:all R=+485.3 p = 5.9e-455 FAIL !!!!!!! [Low8/64]FPF-14+6/4:cross R=+289.0 p = 8.7e-228 FAIL !!!!!! [Low8/64]Gap-16:A R= +20.5 p = 5.5e-17 FAIL ! [Low8/64]Gap-16:B R=+140.6 p = 4.6e-114 FAIL !!!!! ...and 661 test result(s) without anomalies
So, what's happening here? By choosing the worst case (changing just the highest bit),
uncommenting the printf() calls in the code and commenting the fwrite() calls
we obtain:
78b4c0c8b39829c8 b4c0c8b29829c84f 07ae88d0bbb18236 a707ae88c0bbb182 78be926ebaf6613d 0678be926fbaf661 96a5ef3c1b029f66 a5ef3c1f029f66ce 79eec016d1e02600 9579eec006d1e026 78f96c30b953ccb3 f96c30b153ccb319 83bc05c7ee753ca1 3583bc05d7ee753c
The repeated bit patterns in each pair of consecutive outputs are evident even to the naked eye: it is not surprising that so many tests fail. Any change in the initial state leaving intact a sufficiently large number of low bits will reproduce the problem: the repeated patterns will never go away.
Instead, generators using a linear engine such as xoroshiro128++
will decorrelate after a few outputs even if a single bit of
state had been flipped. This is what happens with two such generators initialized
with exactly the same seed of the two PCG generators:
5362d8a01671b995 d362d8a01670b995 0a97246a7e80a888 8a98346a7e81a88a c47b9b0e4dc38c7b 44769b0c35c48b79 4e442a6854dab254 cb883a5234d5f0d4 d6a29eb093c23736 da229bd8bbdb072c 79bb56117df4d1f9 76b2e38b66dfd211 39028d687f5b1025 09737341864c79a8
Larger-state linear generators might require more time, but they will eventually decorrelate. In fact, any sensible pseudorandom generator (not necessarily linear) will mix up quickly a state change (even a single-bit change) and provide an uncorrelated subsequence.
Wrap-up: PCG generators contain a large number of pairs of non-overlapping correlated subsequences.
False claims
We are now discussing just single-sequence generators with w-bit output and w or 2w bits of state. The other options have the severe statistical flaws we discussed.
It is challenging to predict a PCG generator
This claim has appeared originally on Melissa O'Neill website and on her manuscript. There is no evidence for this claim. To me, it has been always evident that PCG generators are very easy to predict. Finally, in 2020 a group a INRIA took up the challenge and showed how to predict a PCG generator using standard cryptoanalytic techniques.
The paper takes a particularly strong variant and solves the problem for a generic increment constant. A couple
of years ago I had shown similar results for another variant, assuming a fixed constant: this program accepts as input the 64-bit state of a PCG
generator, generates three outputs, and recover the original state from the output, making it possible to predict
all future outputs of the generator.
Just compile with -O3 and run.
Writing the function that performs the
prediction, recover(), took maybe half an hour of effort. It's a couple of loops, a couple of if's and
a few logical operations. Less than 10 lines of code.
> ./predpcg 0x333e2c3815b27604
Provided generator state: 333e2c3815b27604
First three outputs: cd9f107b, 8b817ffc, 7c12d316
Recovered generator state (from output): 333e2c3815b27604
Analogously this program accepts as input the 128-bit state of a PCG (same variant and assumptions) generator, generates a few outputs, and recovers the original state from the output, making it possible again to predict all future outputs of the generator. To compile it, you will need Victor Shoup's amazing NTL library. The program uses the same logic of the 64-bit case (and of the INRIA paper)—guessing exhaustively a few bits, deriving a lot of other bits, and solving a simple modular equation. However, in the 64-bit case the equation can be solved by trying all possible solutions, whereas in this case we use a standard technique based on lattice reduction: as a result, discovering the initial state takes usually less time than in the 64-bit case (in fact, the computation time can be brought down to well below a second if you are willing to examine more outputs).
By the same token, it is easy to set the state of a PCG generator so that it outputs a string of
your choice. This program, for example, forces a PCG generator with 128 bits of state to output the string > John D. Cook <.
If you pass its output through hexdump -C, you'll see
00000000 98 06 19 c7 65 5b ce 68 f2 41 47 84 50 cf ba fa |....e[.h.AG.P...|
00000010 a9 eb 2d 00 67 a3 34 af 5a e7 70 31 4b ae a3 38 |..-.g.4.Z.p1K..8|
00000020 03 98 b2 b5 39 0d 05 e3 98 db 33 9f b7 d4 9d b7 |....9.....3.....|
00000030 2c 29 12 34 52 66 ce b7 01 ca 96 3f f3 eb cf 7a |,).4Rf.....?...z|
00000040 d9 76 81 e9 36 e7 06 2b c6 94 0c 66 d0 96 d6 82 |.v..6..+...f....|
00000050 5f b1 c6 18 50 24 19 64 db 0a de 7b 27 28 ab 81 |_...P$.d...{'(..|
00000060 0f 31 0b 5c 37 bd 10 ec 1e 04 da ae 18 ce 9d 4d |.1.\7..........M|
00000070 ff 5c fd 43 fd e6 24 70 23 94 8f 8b 41 0a 89 eb |.\.C..$p#...A...|
00000080 3e 20 4a 6f 68 6e 20 44 2e 20 43 6f 6f 6b 20 3c |> John D. Cook <|
00000090 03 f6 4e 49 4a 39 fa 15 e1 3c 9f e7 bc 78 a9 c0 |..NIJ9...<...x..|
000000a0 ea ea e2 46 65 65 63 b5 81 1b 76 01 c9 28 8b 6d |...Feec...v..(.m|
000000b0 ec a2 0c a4 6b e1 33 d0 55 6f 8a db 49 73 a7 38 |....k.3.Uo..Is.8|
000000c0 6d 33 8c 5b 9a 88 39 ff 70 90 ff 8f 5d 0a a6 75 |m3.[..9.p...]..u|
000000d0 dd d6 2f 5c 44 bc a2 af 71 17 8a d2 f0 a0 cf da |../\D...q.......|
000000e0 f2 3b c5 7b 51 dc 75 50 0f 50 79 8a 5b 9b 7b c4 |.;.{Q.uP.Py.[.{.|
Wrap-up: PCG generators are easy to predict.
PCG generators are fast
They're not. 128-bit operations are slow. On my hardware a 128-bit PCG generators take 2.75ns to
emit an integer, against 0.95ns for xoroshiro128++. The PCG generator is almost three times slower.
And they both pass all statistical tests.
You might want to measure the speed on your hardware: just download the harness and the
benchmark, compile the latter with gcc -O3 -fno-move-loop-invariants -fno-unroll-loops and execute with at least a billion repetitions
(the number of repetitions is the only parameter to the harness). You can also
download the benchmark for xoroshiro128++ and compare. But the idea that manipulating
128-bit numbers can be faster than performing a few 64-bit shifts,
rotations, xors and sums is ridiculous. The PCG generators with the
same number of state and input bits are slightly faster (1.46ns), but still
slower than a xoroshiro128++ generator.
The new design of PCG generators used in NumPy, PCG64DXSM, avoids almost all full 128-bit operations and thus needs just 1.44ns to emit an integer, which is a significant improvement, albeit the timings are still far from the sub-ns area of scrambled linear generators or 64-bit MWC generators of similar size.
Said that, I will repeat again: you have to measure the speed of your PRNG inside your application. These
figures are just an indication. Even better, you might want to check the
results of the Intel®
Architecture Code Analyzer, which reports 3.50 cycles for xoroshiro128++,
a whopping 9.53 cycles for a 128-bit PCG generator, and
5.53 cycles for PCG64DXSM.
Wrap-up: while PCG generators are not terribly slow, they are very far from the sub-ns performance of fast scrambled linear generators.
Conclusions
Wrap-up: There is technically no sensible reason to use a PCG generator: those without flaws are not competitive.
Nonetheless, you might wish to use at all costs, for some reason, a PRNG based on congruential arithmetic with 64 bits of output, 128 bits or more of state, and using 128-bit multiplications.
In that case, you have a much better option: Marsaglia's Multiply-With-Carry generators and their generalizations. For example, MWC128 is a generator with 128 bits of state that is much faster than a PCG generator, and the design can be extended, say, to 256 bits of state.
The generators above pass all statistical tests, but have a few theoretical defects, which are partially fixed by a generalized version defined by Goresky and Klapper: GMWC128 and GMWC256. GMWC generators, however, are about twice slower than MWC generators.
The generators with 128 bits of state have period ≈2127 (more precisely, there are two orbits of size ≈2127, and after very few steps you will fall into one). Analogously, the generators with 256 bits of state have period ≈2255.
Subsequences of these generators will be uncorrelated except in very special cases—when the initial states of the associated linear congruential
generator differ by a small multiplicative constant; but these cases can be easily avoided, for example, by seeding the carry c with a fixed constant.