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 the claims made by Melissa O'Neill on the remaining PCG generators, and provide simple counterexamples for each claim. In the end, we define a new, simple LCG-based generator that is faster and has the same statistical properties of the only remaining 64-bit PCG generator. The conclusion is that there is no reason to use PCG generators: for those without statistical flaws, there is always a better LCG-based 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) after 100,000 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


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 will work without problems: but 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

and seemingly random increments

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.

Wrap-up: Do not use PCG generators with multiple sequences.

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. Of course, no security expert ever tried to to that: it would be like beating 5-year-old kid on a race. It would be embarrassing.

So we had this weird chicken-and-egg situation: nobody who could easily predict a PCG generator would write the code, because they are too easy to predict; but since nobody was predicting a PCG generator, Melissa O'Neill kept on the absurd claim that they were challenging to predict.

I just decided to break the loop: this program accept as input the 64-bit state of a PCG generator, generates three outputs, and recover from the output the original state, making it possible to predict all future outputs of the generator. Just compile with -O3 and run. Note that it is impossible to approach the problem by brute force: to try blindly all possible 264 states you would need centuries of time.

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 (of course this can be improved, made faster, etc.).

        > ./predpcg 0x333e2c3815b27604
        Provided generator state: 333e2c3815b27604
        First three outputs: cd9f107b, 8b817ffc, 7c12d316
        Recovered generator state (from output): 333e2c3815b27604

Does this look “challenging”?

Wrap-up: PCG generators are easy to predict.

PCG generators remain random when a bijection is applied to their output

Commenting negatively our new xoshiro256** generator, Melissa O'Neil did a quite interesting thing: she looked into the generator and “undid” part of the scrambling. This backward operation uncovered a few bits (about 5) which have low linear degree, so PractRand could detect a failure in the (quite innocuous) binary-rank test.

Now, this is not very sensible because these are not secure PRNG: you are supposed to test the PRNG, not attack it. In particular the tests you use should not use knowledge of the inner workings of the PRNG. This is why, by the way, many people consider failures in linearity tests (such as binary rank and linear complexity) not very relevant: they were designed with some knowledge of the PRNG.

But what absolutely amazes me is that Melissa O'Neill understands so little of PRNGs that she didn't realize her own PRNGs do not pass her own test (quite obviously, I would add).

I wrote a simple program that takes a PCG generator and applies a very simple bijection: the output is xor'd with itself, shifted right by 43 positions. The stream is written to standard output, and you can pipe it into PractRand. This bijection leaves 2/3 of the bits untouched: it is much simpler than the multiplications Melissa O'Neill used in her criticism of xoshiro256**.

So let's run the program and see what PractRand says. Following Melissa O'Neill criterion, we should see a random stream:

        rng=RNG_stdin64, seed=0x3990d5ed
        length= 8 gigabytes (2^33 bytes), time= 56.4 seconds
          Test Name                         Raw       Processed     Evaluation
          [Low4/64]BCFN(2+2,13-2,T)         R= +11.8  p =  1.3e-5   suspicious
          [Low4/64]BCFN(2+3,13-2,T)         R= +23.4  p =  1.4e-11    FAIL
          [Low4/64]BCFN(2+4,13-3,T)         R= +22.4  p =  2.0e-10   VERY SUSPICIOUS
          [Low4/64]BCFN(2+5,13-3,T)         R=+100.8  p =  1.6e-47    FAIL !!!
          [Low4/64]Gap-16:A                 R= +47.8  p =  1.8e-39    FAIL !!!
          [Low4/64]Gap-16:B                 R= +36.3  p =  5.2e-32    FAIL !!!
          [Low4/64]FPF-14+6/16:(0,14-0)     R= +27.4  p =  6.3e-25    FAIL !!
          [Low4/64]FPF-14+6/16:(1,14-0)     R= +17.6  p =  6.1e-16    FAIL
          [Low4/64]FPF-14+6/16:(2,14-0)     R= +12.7  p =  2.3e-11   VERY SUSPICIOUS
          [Low4/64]FPF-14+6/16:(3,14-0)     R=  +6.8  p =  7.1e-6   unusual
          [Low4/64]FPF-14+6/16:all          R= +28.7  p =  1.9e-26    FAIL !!
          [Low4/64]FPF-14+6/16:all2         R=+245.4  p =  1.4e-98    FAIL !!!!!
          [Low4/64]FPF-14+6/16:cross        R= +12.4  p =  8.6e-11   VERY SUSPICIOUS
          [Low1/64]BCFN(2+0,13-3,T)         R= +18.6  p =  1.4e-8    VERY SUSPICIOUS
          [Low1/64]BCFN(2+1,13-3,T)         R= +24.2  p =  2.9e-11    FAIL
          [Low1/64]BCFN(2+2,13-3,T)         R=  +8.0  p =  1.5e-3   unusual
          [Low1/64]BCFN(2+3,13-3,T)         R= +34.8  p =  2.9e-16    FAIL !
          [Low1/64]Gap-16:A                 R= +21.0  p =  2.1e-17    FAIL !
          [Low1/64]FPF-14+6/16:(0,14-0)     R= +23.3  p =  3.3e-21    FAIL !
          [Low1/64]FPF-14+6/16:(1,14-0)     R= +17.4  p =  1.0e-15    FAIL
          [Low1/64]FPF-14+6/16:(2,14-0)     R=  +6.9  p =  5.9e-6   unusual
          [Low1/64]FPF-14+6/16:(3,14-1)     R=  +6.9  p =  7.5e-6   unusual
          [Low1/64]FPF-14+6/16:all          R= +27.1  p =  6.2e-25    FAIL !!
          [Low1/64]FPF-14+6/16:all2         R=+190.0  p =  1.4e-72    FAIL !!!!
          [Low1/64]FPF-14+6/16:cross        R=  +7.0  p =  3.0e-6   suspicious
          ...and 187 test result(s) without anomalies

This it not an innocuous failure in a linearity test: this is a disaster, and in particular a major failure in one of the oldest and most important tests, the gap test.

In other words, PCG generators catastrophically fail Melissa O'Neill criterion of randomness.

Now: I'm not claiming this criterion is sensible. But if you think it is, the results above show say you should stay away from PCG generators.

Wrap up: you can believe in this criterion or not; whichever your position, PCG generators fail in a much more severe way this test than xoshiro256**.

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 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, but still slower than a xoroshiro128** generator (1.46ns).

Said that, I will repeat again: you have to measure the speed of your PRNG inside your application. These figures are just an indication.

Wrap-up: while PCG generators are not terribly slow, they are very far from the sub-ns performance of fast scrambled linear generators.


Wrap-up: There is technically no sensible reason to use a PCG generator: those without flaws are not competitive.

However, you might wish to use at all costs, for some reason, an LCG-based PRNG with 64 bits of output and 128 bits of state.

In that case, I suggest that you do the simplest thing: take a good 128-bit LCG (the parameters can be copied from Pierre L'Ecuyer's classical paper—Melissa O'Neill did the same) and then apply to the high bits a good, standard mixing function, like the variant of the MurmurHash3 finalization step used by Java's SplittableRandom: we could call this brand new generator LCG128Mix.

        #include <stdint.h>

        __uint128_t x;

        uint64_t inline next(void) {
            // Put in z the top bits of state
            uint64_t z = x >> 64;
            // Update state
            x = x * ((__uint128_t)0x2360ed051fc65da4 << 64 ^ 0x4385df649fccf645)
                  + ((__uint128_t)0x5851f42d4c957f2d << 64 ^ 0x14057b7ef767814f);
            // Compute mix
            z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
            z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
            return z ^ (z >> 31);

This generator is faster than a 128-bit PCG generator: just 2.16ns per word (but benchmark on your hardware). You'll have a very strong 128-bit LCG-based generator (it will even pass the criterion so catastrophically failed by PCG generators), and you'll be standing on the shoulders of giants.