Lair Of The Multimedia Guru

In the previous blog entry I showed many bad correlations in PCG-DXSM, but the cases had always at least 2 values non random either a seed and an increment or 2 increments. And even though one could create more than a septillion of these for each seed/increment. Thats not how PCG-DXSM should be used.

So the natural question is, can this happen if PCG-DXSM is used how its supposed to, that is initialized with strongly random seed+increment.

The short awnser is, given the right circumstances, yes.
The following text is structured like this:

1. Some basic and known concepts about LCGs to better illustrate their structure
2. Summary of what we currently know about the correlations
3. Some actual tests and software to quantify these specific correlations
4. A hypothetical example showing that this can be a real issue under the right circumstances
5. A workaround
6. A Solution
7. Some final words
8. More issues

Some basic and known concepts about LCGs to better illustrate their Structure

In the algebraic structure of LCGs with identical multipliers and operations mod 2^m
LCG(v₀, increment) can be seen as a vector whos elements are defined by v_i = v_i-1 * multiplier + increment (mod 2^m) we can add 2 vectors and thus LCGs. LCG(seed1, increment1) + LCG(seed2, increment2) = LCG(seed2+seed1, increment2+increment1) from this we can immediately see that the associative and kommutative law holds and that there is a inverse and identity element.
Thus LCGs with identical multipliers form an abelian group. The identity element is LCG(0,0)_i = 0. For each constant vector v_i = C theres a corresponding LCG(C, C*(1 – multiplier)) the increment of such “bad” LCGs is even when the multiplier is odd. It is thus common to disallow even increments. None the less even when they are disallowed in an implementation, they do not disappear from the algebraic structure. Thats because if one allows only odd numbers
the difference between 2 odd numbers is still even. If we looked at LCGs as polynomials instead of vectors then we could furthermore introduce a multiplication by x mod x^{2^M}-1 to represent a cyclic shift of all the elements of one vector. This would allow even more powerful tools to be used. But we don’t do this currently in this text. What we now have is basically a very small set of “primitive” LCGs that can then be offseted by a constant
LCG(C,I + C*(1 – multiplier)) = LCG(0,I) + LCG(C, C*(1 – multiplier)) the number of these primitive LCGs depend on the number of factors of 2 in 1 – multiplier. for PCG-DXSM we have 2 factors of 2 but odd increments are disallowed so we have 2 such primitive vectors which is all the diversity that exists in this LCG, all other vectors are just offseted by a constant from them. Looking at this you might ask if there are 2 LCG outputs that have a 128bit constant added how do these 2¹²⁹ cases fit in a 127bit “odd” increment. They do because 4 live as cyclic shifts in each vector.

Summary of what we currently know about the correlations

In the previous section we have shown that we can offset the LCG output by a constant and that all LCG outputs basically are offseted from one of 2 sequences by a constant. Or if one considered the 4 cyclic shifts too then really only half would be unique, its a matter of viewpoint.

Offsets in the low half

In DXSM the LCG output is split in 2 64bit words the low one or-ed by 1 so its always odd and the high one passed through xorshift, multiply, xorshift
before being multiplied with the low.
If we look at 2 LCGs that are offseted by D, so that only the low half is offsetted but the high half stays the same. This can be represented (in C style notation) as:
(L[i] | 1)*H[i] vs. ((L[i] + D) | 1)*H[i]
both (L[i] | 1) and ((L[i] + D) | 1) are odd as they have explicitly an 1 or-ed in, this can be written also as
(2X[i] + 1) * H[i] vs. (2Y[i] + 1) * H[i]
their difference
(2X[i] + 1)*H[i] – (2Y[i] + 1)*H[i] = (2X[i] + 1 – 2Y[i] – 1)*H[i] = 2(X[i] – Y[i])*H[i]
as can be seen their difference is even thus their lowest bit is correlated, that is not to say higher bits are not
Here we now have established that instead of 2¹²⁷ uncorrelated PCG-DXSM streams there are at best 2⁶⁴

Collisions in the first xor

The first xor mixes the high 32bit of the high half into the low 32bit of the high half, next the high half is multiplied by the constant multiplier and the high quarter xored into the low quarter before the final multiplication with the low half of the LCG. It is important to recognize that if, after the first XOR the low 49bits of the high side of the LCG match between 2 generators then we will have identical low bits after DXSM. Consider
MSB [15bit random][17bit 0][15bit random][17bit 0][64 bit random] LSB
The first xor stage will effectively do nothing to this. The correlation after that then depends on the low 15 random bits which is the only difference there is between the two LCGs which can affect the LSB from the high half. While the low half is orred by 1 so it is bascially a constant. If this on its own doesnt already fail statistical tests. Then this can be made more likely by observing that if we misalign 2 LCGs by a multiple of 2^128-b the only affected output will be in the highest b bits. So we can introduce entropy in the highest bits at will to tweak the high quarter and bring the 2 into a bad correlated state. The high quarter itself is outside the 49bits affecting the LSB output other than by the xor. It is also observed that increasing the amount of random bits beyond 15 does not fix this issue. It just requires more effort to find correlations. For example using 19bits, 65536 streams, 1024 stream alignments and 4 billion samples per stream, we still find statistical anomalies.

Collisions in the 2nd xor

It is possible to introduce a delta in the low half of the high half of the LCG, this will be unaffected by the first xor and then multiplied by the multiplier, this operation is algebraically well understood and it is possible to introduce deltas here which tend to produce poor statistics after the 2nd XOR on the low side. Such a case was also demonstrated toward teh end of my last blog entry, but no attempt was made to exploit this in the software here

Some actual tests and software to quantify these specific correlations

Combining the 2 cases from above with 19bits instead of 15 we can take 16k random increment,seed pairs and find a pair of vectors that are correlated if they are aligned. I cannot show correlation directly on fully random values due to myself only having my home computer for this. Also I do take 64k instead so we have over a dozend pairs to work with. At this point we align one of the seeds to the other, then shift it by a random 2^128-19 multiple and check the correlation for 1024 shifts. For each shift we generate a stream of 2³² values. Each tested stream will have its least significant bits interleaved or xored and the occurrence of each even 2-18 bit pattern checked based against the binomial distribution. Both the xor and interleaving sometimes catch separate cases so either alone could be used for slightly fewer cases found. Also for XOR mainly 6 and 8 bits matter while for interleaving the larger ones catch things. In the test run we see a pair that showed correlations at 15 different alignments of the 1024 tested. Given these 1024 represent a random 1/512 of the searchspace we consider. We expect ~8000 in the whole space for that pair. Other pairs had similar numbers so theres no reason to believe this was a outlier. Combining all this there seems to be a maximum of ~29 bits of diversity in the increments and about 115 bits in the seed. We can also see that many of the found correlations have multiple independent patters that are failing tests
Source code is here

Stage 1, filling set with random increments
set size:65536, stream_length:4294967296, top bits:19
Stage 2, Sorting streams
Stage 3, Comparing streams
pairs to consider: 37
checking pair with DELTA: 0xE5B05FFFA33E1FFF ED6E8B7EA831BA19 si0: 0x4B1D7EBE754531A6 03D07FC29934A58B,0xEC1A098AE7F3EE1C F0C3F7E28050E655 si1: 0x656D1EBED20711A6 1661F443F102EB72,0xCFC64EE4226C353F 911E2DDFC6D557E9
clean table 32 18
fill table 32 18
clean table 32 16
fill table 32 16
clean table 32 14
fill table 32 14
clean table 32 12
fill table 32 12
clean table 32 10
fill table 32 10
clean table 32 8
fill table 32 8
clean table 32 6
fill table 32 6
clean table 32 4
fill table 32 4
clean table 32 2
fill table 32 2
 3B8:  DELTA: 0xE3DF5FFFA33E1FFF ED6E8B7EA831BA19 -6    6(  67044071)0.000000008
checking pair with DELTA: 0x2FC51FFF99D95FFF B54A758B34402CFA si0: 0x6AF7AD68373F1ECB 388F5B99D012EDC8,0x3E41C67901EE75A1 DDAC6EB90EFCDF53 si1: 0x3B328D689D65BECB 8344E60E9BD2C0CE,0xD540FAF60FD83D88 C4D70A7957646F1B
checking pair with DELTA: 0x069F600086C96000 0EB818571D7DCAD0 si0: 0x75FED5AD724E4D47 09756BA7A9BB3730,0x11E1922B5FBB1E8E 4F7311398EE8460F si1: 0x6F5F75ACEB84ED46 FABD53508C3D6C60,0x9AAEFF3A5B76A3D6 3EC2E876DEA2604F
checking pair with DELTA: 0xA6DBFFFFA9631FFF ECCA24CFB00F1167 si0: 0x642B9E142D73D47D 758CA1A36D0AED70,0xEA0B9F70E0FE5C84 59DF4DCDE2F4727F si1: 0xBD4F9E148410B47D 88C27CD3BCFBDC09,0x893A4A4B113A5A3C 205C596A9D7316EB
checking pair with DELTA: 0xA4107FFF2C3EC000 26C54851149E853A si0: 0xE76E9BF9B19A825A 6A986886330B2129,0x1090288CC2863F81 D609776DF7909853 si1: 0x435E1BFA855BC25A 43D320351E6C9BEF,0xCD67E2DED5A42A3C 1905C3FB9FE4351B
  AE:  DELTA: 0xEB3EBFFF2C3EC000 26C54851149E853A 12  310(   1057180)0.000000015  12  290(   1056853)0.000000211  12  f10(   1056627)0.000001252  12  1a0(   1040569)0.000001519  12  6e0(   1056277)0.000017950  12  690(   1041143)0.000113557  12  560(   1055904)0.000270395  12  da0(   1041278)0.000299401
 32E:  DELTA: 0x5DEEBFFF2C3EC000 26C54851149E853A 12  5c0(   1038624)0.000000000  12  1c0(   1057931)0.000000000  12  ec0(   1057333)0.000000004  12  ac0(   1040326)0.000000223  12  dc0(   1056653)0.000001023  12  6c0(   1041181)0.000149446  12  2c0(   1055845)0.000410364  12  9c0(   1041636)0.003602710
 2AE:  DELTA: 0x46FEBFFF2C3EC000 26C54851149E853A 12  4d0(   1060953)0.000000000  12  610(   1062490)0.000000000  12  760(   1060287)0.000000000  12  7a0(   1058928)0.000000000  12  8d0(   1063077)0.000000000  12  a10(   1062087)0.000000000  12  b60(   1062943)0.000000000  12  ba0(   1061416)0.000000000
 22E:  DELTA: 0x300EBFFF2C3EC000 26C54851149E853A 12  670(   1057881)0.000000000  12  740(   1039293)0.000000000  12  580(   1040335)0.000000239  -6    c(  67168834)0.000000783  12  570(   1056351)0.000010320  -6   2c(  67053163)0.000034817  12  f40(   1056076)0.000078670  12  d70(   1041141)0.000111924
checking pair with DELTA: 0x50007FFF5C726000 B744241DE30B69D1 si0: 0x6B787EBE72991EEA 8289751974A2A05F,0x0BBD42A86319A4D6 1545348A20D29269 si1: 0x1B77FEBF1626BEE9 CB4550FB9197368E,0xA41D07785110511F 469B72942EA5D15D
checking pair with DELTA: 0x4AC8DFFF76E85FFF 5317B9650AE16599 si0: 0x87FB5321F119AC7A C56465440DFD6BBB,0x1BC3CB3CF5D7B874 DACCF5D5C924B5AF si1: 0x3D3273227A314C7B 724CABDF031C0622,0x07EE1FA4549F8160 7A648121E3A1BD43
checking pair with DELTA: 0x0D78BFFFF0FCC000 9F272846B576856A si0: 0x114FA1E4F4E52E77 6CF38EB5E44CC81B,0x79DA1F7A3E715F59 889363DD36B59C95 si1: 0x03D6E1E503E86E76 CDCC666F2ED642B1,0x4998AE764CF9EA36 A31FDF6D2069DB1D
 2F9:  DELTA: 0xF300DFFFF0FCC000 9F272846B576856A 1834a80(     17652)0.000000000  16  540(     68674)0.000000000  16  a80(     68749)0.000000000  16 1740(     68320)0.000000000  16 1a40(     68301)0.000000000  16 2740(     68147)0.000000000  16 2a40(     68350)0.000000000  16 3540(     68046)0.000000000
 3F9:  DELTA: 0xA420DFFFF0FCC000 9F272846B576856A 14 2000(    266373)0.000000215  16 3000(     63697)0.002678040  14    0(    258663)0.011878566  16 8000(     63794)0.041411834  14 1000(    265545)0.041734621
checking pair with DELTA: 0xBBE320004FF76000 82454C2874A21EF3 si0: 0x7BBAE3DB04A0B4DE 5D7DAF8022BF2D34,0xB6D14DEA456CF025 AF3C8E5BC500FBDD si1: 0xBFD7C3DAB4A954DD DB386357AE1D0E41,0x2E36E70296EAF807 09177110A56946B9
 109:  DELTA: 0xA338C0004FF76000 82454C2874A21EF3 -6   24(  67168303)0.000001275  -6    4(  67058944)0.003937258
 309:  DELTA: 0x0478C0004FF76000 82454C2874A21EF3 16 1000(     68200)0.000000000  16 6000(     67912)0.000000000  16 9000(     68422)0.000000000  16 a000(     68296)0.000000000  16 e000(     68322)0.000000000  14 1000(    271534)0.000000000  14 2000(    272358)0.000000000  14    0(    247561)0.000000000
 189:  DELTA: 0x3B88C0004FF76000 82454C2874A21EF3 14 3523(    266414)0.000000110  14  523(    266255)0.000001424  14 17a3(    266247)0.000001616  14 3e23(    266166)0.000005727  14  52f(    266127)0.000010440  -8   e8(  16806671)0.000011400  14 34a3(    266115)0.000012545  14  223(    266025)0.000048894
 389:  DELTA: 0x9CC8C0004FF76000 82454C2874A21EF3 14 239c(    265963)0.000122652  -8   f8(  16749417)0.000200331  14  f9c(    265926)0.000210908  14 3cac(    265900)0.000307758  -8   38(  16803599)0.002137644  -8   78(  16751532)0.006391691  14   ac(    258625)0.007053808  14 1c6c(    265614)0.016667751
checking pair with DELTA: 0x61F81FFFD0A1A000 0EDB22A63E0AD996 si0: 0x1429D0EE8B94E764 E8B02AFD0694AD82,0x17D8D7C4708639FC F80DBC31B69114A5 si1: 0xB231B0EEBAF34764 D9D50856C889D3EC,0x79A6C972B0378F58 9787503C7F7BA21D
 12C:  DELTA: 0x41639FFFD0A1A000 0EDB22A63E0AD996 14  82c(    267011)0.000000000  14 1bdc(    257159)0.000000000  14 282c(    257273)0.000000000  14 275c(    257468)0.000000000  14 342c(    266806)0.000000000  14 182c(    257848)0.000000050  14 27dc(    257918)0.000000159  14  75c(    266276)0.000001021
  2C:  DELTA: 0xBCC39FFFD0A1A000 0EDB22A63E0AD996 14  65c(    257898)0.000000114  14 19ac(    266391)0.000000161  14 15ac(    266117)0.000012167  14 29ac(    265981)0.000094048  14 332c(    258649)0.009809622  14 365c(    258698)0.019104299  14 3a5c(    258709)0.022160153
 2EC:  DELTA: 0x697B9FFFD0A1A000 0EDB22A63E0AD996 14 202b(    265734)0.003239245
 32C:  DELTA: 0x4AA39FFFD0A1A000 0EDB22A63E0AD996 14 20ac(    266407)0.000000124  14 2fec(    258349)0.000135828  14 3e6c(    258354)0.000146280  14 10dc(    258396)0.000271643  14 30dc(    265864)0.000517196  14 2f2c(    258539)0.002125153  14  aec(    265729)0.003471746  14 3fec(    265693)0.005703141
 2AC:  DELTA: 0x88539FFFD0A1A000 0EDB22A63E0AD996 16 2c00(     67872)0.000000001  16 ec00(     67853)0.000000001  16 9c00(     63245)0.000000001  16 ac00(     63262)0.000000002  16 6c00(     63316)0.000000014  16 5c00(     63339)0.000000031  16 1c00(     67614)0.000003283  16 dc00(     67613)0.000003389
 22C:  DELTA: 0xC6039FFFD0A1A000 0EDB22A63E0AD996 14  56c(    266846)0.000000000  14  3ec(    266323)0.000000482  14  96c(    266299)0.000000708  14 105c(    258276)0.000045522  14 13dc(    258308)0.000073692  14 3a9c(    265995)0.000076435  14  c1c(    265955)0.000137963  14  a9c(    265801)0.001268171
checking pair with DELTA: 0xAEE04000493CBFFF BD570161F1BB9245 si0: 0x3232CB36E1EE4D2A A6E5C02AEC015417,0x5D4AADB8CE05CB16 60BFF633BE1922B7 si1: 0x83528B3698B18D2A E98EBEC8FA45C1D2,0x7023209E9838B9CB EDC7AD26E9D4B33B
  FA:  DELTA: 0x91C80000493CBFFF BD570161F1BB9245 16    0(     67945)0.000000000  14 1270(    267234)0.000000000  12   80(   1061964)0.000000000  12  1b0(   1059972)0.000000000  12  270(   1062824)0.000000000  12  34c(   1059060)0.000000000  12  40f(   1058356)0.000000000  12  540(   1062857)0.000000000
checking pair with DELTA: 0xF1602000180CDFFF DDB3EEC70873FC23 si0: 0xCD641FA73D4FFD4D C1BFB916CB540340,0xD46851900454DC91 BE71D8204442D5E5 si1: 0xDC03FFA725431D4D E40BCA4FC2E0071D,0xDD28B58BCA390DD0 200B20AFEAB32681
 149:  DELTA: 0x46ACC000180CDFFF DDB3EEC70873FC23 -8   40(  16748835)0.000073773  -8   48(  16804298)0.000682072  14 161c(    265780)0.001704525  12  e5c(   1041888)0.019305183
  49:  DELTA: 0xBF0CC000180CDFFF DDB3EEC70873FC23 12  1ac(   1058326)0.000000000  12  dac(   1059512)0.000000000  -6    0(  67180422)0.000000000  -6   20(  67037873)0.000000000  12  5ac(   1039647)0.000000001  12  e5c(   1056936)0.000000108  12  9ac(   1040522)0.000001052  12  25c(   1056402)0.000007026
 249:  DELTA: 0xCE4CC000180CDFFF DDB3EEC70873FC23 12  16c(   1039873)0.000000005  12  69c(   1056832)0.000000250  12  920(   1040498)0.000000872  12  750(   1040800)0.000008950  12  56c(   1055931)0.000223162  12  f50(   1055478)0.005111395  12  e9c(   1041846)0.014654417  12  350(   1055194)0.033027892
  C9:  DELTA: 0x82DCC000180CDFFF DDB3EEC70873FC23 16    0(     67311)0.024882147
 209:  DELTA: 0xEC64C000180CDFFF DDB3EEC70873FC23 14  edb(    258766)0.047457856
 3C9:  DELTA: 0x19BCC000180CDFFF DDB3EEC70873FC23 12  e7c(   1059061)0.000000000  12  a7c(   1039130)0.000000000  12  98c(   1039273)0.000000000  12  58c(   1039733)0.000000002  12  880(   1057062)0.000000039  12  c80(   1040191)0.000000075  12  27c(   1056979)0.000000077  12  18c(   1056842)0.000000230
 1C9:  DELTA: 0x0A7CC000180CDFFF DDB3EEC70873FC23 12   b0(   1058704)0.000000000  12  870(   1058321)0.000000000  12  cb0(   1058044)0.000000000  12   70(   1039197)0.000000000  12  380(   1057886)0.000000000  12  3b0(   1039348)0.000000000  12  470(   1057815)0.000000000  12  770(   1039485)0.000000000
checking pair with DELTA: 0x4BAEDFFF3117BFFF 2C6645F93365ECEA si0: 0xE40A9D2B0465523F 42BC3B3B97D36E8D,0xBB93AB3A34C78A9A 64593536E5C52775 si1: 0x985BBD2BD34D9240 1655F542646D81A3,0x3AB79415CB425F3D 57648C6C00E22BFD
 194:  DELTA: 0x51A95FFF3117BFFF 2C6645F93365ECEA 12  d39(   1041947)0.028354029
checking pair with DELTA: 0x98E3E00009FCA000 0A0A41967884F5D6 si0: 0xDF60BAED6D489376 8C513233A6ED5E42,0x3955813EEBEECC4A 641A81300E22E3A5 si1: 0x467CDAED634BF376 8246F09D2E68686C,0x5ACFED56DDFFBB1B A8D2EF5151DF4E1D
  FF:  DELTA: 0xBD3F400009FCA000 0A0A41967884F5D6 12  507(   1041478)0.001219788
 11F:  DELTA: 0xC5D3400009FCA000 0A0A41967884F5D6 12  5fe(   1041919)0.023635555
 31F:  DELTA: 0x4F13400009FCA000 0A0A41967884F5D6 -6   33(  67163521)0.000085788
  9F:  DELTA: 0xA383400009FCA000 0A0A41967884F5D6 12  eee(   1041253)0.000250523  12  d1e(   1055609)0.002107609  12  dee(   1041717)0.006220077
 37F:  DELTA: 0x68CF400009FCA000 0A0A41967884F5D6 12   db(   1058017)0.000000000  12   e7(   1058942)0.000000000  12  7db(   1059479)0.000000000  12  827(   1059615)0.000000000  12  ce7(   1058144)0.000000000  12  f27(   1058944)0.000000000  -8   66(  16826582)0.000000000  -8   e6(  16822338)0.000000000
 27F:  DELTA: 0x242F400009FCA000 0A0A41967884F5D6 14 34a7(    267131)0.000000000  12   5b(   1064451)0.000000000  12   bb(   1060051)0.000000000  12  137(   1064641)0.000000000  12  14b(   1059721)0.000000000  12  1cb(   1063913)0.000000000  12  227(   1058434)0.000000000  12  237(   1062931)0.000000000
  7F:  DELTA: 0x9AEF400009FCA000 0A0A41967884F5D6 -6   12(  67240251)0.000000000  -6   32(  66978036)0.000000000  -8   52(  16812266)0.000000000  -8   b2(  16742497)0.000000000  12  997(   1057305)0.000000005  -8   72(  16743940)0.000000008  -8   12(  16809826)0.000000030  12  d6b(   1040123)0.000000043
 29F:  DELTA: 0x2CC3400009FCA000 0A0A41967884F5D6 12  61e(   1041497)0.001391186  12  729(   1055557)0.003001539  12  91e(   1041758)0.008181266  12  f29(   1041977)0.034431422
 2FF:  DELTA: 0x467F400009FCA000 0A0A41967884F5D6 -6    a(  67162084)0.000284374  12  c17(   1041969)0.032696417
  3F:  DELTA: 0x89C7400009FCA000 0A0A41967884F5D6 -6   10(  67060938)0.017930280
 21F:  DELTA: 0x0A73400009FCA000 0A0A41967884F5D6 12  4c1(   1055397)0.008769471
 1FF:  DELTA: 0x01DF400009FCA000 0A0A41967884F5D6 -6   12(  67158377)0.005435176  12  ceb(   1055462)0.005689278
  5F:  DELTA: 0x925B400009FCA000 0A0A41967884F5D6 12  8c6(   1055190)0.033889247
 3FF:  DELTA: 0x8B1F400009FCA000 0A0A41967884F5D6 -6    6(  67166263)0.000008006  -6   26(  67061803)0.033983055
 17F:  DELTA: 0xDF8F400009FCA000 0A0A41967884F5D6 12   17(   1059398)0.000000000  12   c7(   1058635)0.000000000  12   f7(   1058936)0.000000000  12  15b(   1059633)0.000000000  12  1a7(   1061491)0.000000000  12  25b(   1061656)0.000000000  12  2a7(   1061160)0.000000000  12  307(   1058587)0.000000000
checking pair with DELTA: 0x9C385FFFD517C000 306C5C1B4D5AB7C6 si0: 0x3FEAE99F258B5DE7 09F745C8569D55EC,0x7F3878FC16BE1A2D 2DD9E922BA431F8B si1: 0xA3B2899F50739DE6 D98AE9AD09429E26,0xAAC4D1CD87D69C2E 70FEC2F54B2666C3
 2D6:  DELTA: 0x2D609FFFD517C000 306C5C1B4D5AB7C6 14 3eb0(    266018)0.000054283
checking pair with DELTA: 0x886D80002EBC1FFF EBA31452485D63B9 si0: 0xBF85BAB7F7A88915 DD24DFCE63656BDD,0x1D5F2A9E89966A03 3142879BE63649DD si1: 0x37183AB7C8EC6915 F181CB7C1B080824,0xC92276BC926F7002 47E39578BCDCFFF1
checking pair with DELTA: 0x3043000012E7A000 4F55B89E15612A9D si0: 0xB52CE7856DE4DCAE 576D37344D0DE947,0x9055C7B98826164F 4FAAEB6EB2A3DC9F si1: 0x84E9E7855AFD3CAE 08177E9637ACBEAA,0xA6DE91805DB5FD1D B80EAD3EBF24CB03
checking pair with DELTA: 0xDB780000301CDFFF EFC16152F51E792F si0: 0x63684BE2D0185347 9CCA1B957F53D05A,0x80FA168A7F074369 F0A5BC2519C96861 si1: 0x87F04BE29FFB7347 AD08BA428A35572B,0x5B97EE447686113E FB2C8C166671C56D
  8B:  DELTA: 0x37BD6000301CDFFF EFC16152F51E792F 14 3f77(    257778)0.000000015  14 1f77(    266226)0.000002249  -8   f6(  16747303)0.000004836  14   8b(    258467)0.000761714  14  e4b(    258533)0.001952468  14 208b(    265599)0.020378990  -8   b6(  16801849)0.032928680  14 1e4b(    265538)0.045762519
 1CB:  DELTA: 0x1AE56000301CDFFF EFC16152F51E792F -8   90(  16809736)0.000000035  -8   d0(  16749917)0.000465123  -8   10(  16803470)0.002631082
 28B:  DELTA: 0x6FFD6000301CDFFF EFC16152F51E792F -8   3a(  16812939)0.000000000  -8   fa(  16744839)0.000000045  -8   7a(  16749044)0.000105850  -8   92(  16749408)0.000197290  -8   12(  16750130)0.000662933  -8   ba(  16802080)0.023187546  -8   52(  16802065)0.023723934
 3CB:  DELTA: 0x53256000301CDFFF EFC16152F51E792F 14  1ec(    266870)0.000000000  14  bec(    267106)0.000000000  14  e1c(    267279)0.000000000  14 149c(    266995)0.000000000  14 18dc(    267103)0.000000000  14 249c(    267132)0.000000000  14 3e1c(    267193)0.000000000  14  49c(    257280)0.000000000
 38B:  DELTA: 0x8C1D6000301CDFFF EFC16152F51E792F 14 3f07(    265916)0.000243974  14 1c0b(    265914)0.000251174  14  c0b(    258412)0.000343271  14 38b7(    265749)0.002629606  14 20fb(    258612)0.005894475  14 23f7(    265565)0.032043522  14 30fb(    265540)0.044574402
 18B:  DELTA: 0x53DD6000301CDFFF EFC16152F51E792F 14 3c67(    266192)0.000003825  14  39b(    266165)0.000005816  -8   d2(  16747988)0.000016635  14 2f9b(    266035)0.000042097  14 3067(    258273)0.000043503  14 2c67(    258349)0.000135828  14  7d7(    265938)0.000177004  -8   92(  16804377)0.000598385
 24B:  DELTA: 0xA8F56000301CDFFF EFC16152F51E792F 14 1480(    265808)0.001148715
checking pair with DELTA: 0xAC575FFFEABDA000 4916E783B7945A0F si0: 0xEA55F2E4610D825A C9C89FD187E1A389,0xA809E3872B037628 4612D5C116F50F8F si1: 0x3DFE92E4764FE25A 80B1B84DD04D497A,0x88A56FF680022BCF 6C25989E452C8A1B
   B:  DELTA: 0x363E7FFFEABDA000 4916E783B7945A0F -6   12(  67172158)0.000000033

real	519m55,784s
user	13633m42,794s
sys	8m12,787s

Stage 1, filling set with random increments
set size:16384, stream_length:4294967296, top bits:19
Stage 2, Sorting streams
Stage 3, Comparing streams
pairs to consider: 5
checking pair with DELTA: 0xBF6CFFFFE20A6000 1237BFB750ABC5D4 si0: 0x7B36DD275880DB17 CADB2D976848C718,0xF82B95907E57998B 00CC0B074806B4AB si1: 0xBBC9DD2776767B17 B8A36DE0179D0144,0x9B02AF6C89EFC1D7 EA92FCC9A4D2ADBB
clean table 32 18
fill table 32 18 to 4220518
clean table 32 16
fill table 32 16 to 4299161
clean table 32 14
fill table 32 14 to 4613734
clean table 32 12
fill table 32 12 to 5872025
clean table 32 10
fill table 32 10 to 10905190
clean table 32 8
fill table 32 8 to 31037849
clean table 32 6
fill table 32 6 to 111568486
clean table 32 4
fill table 32 4 to 433691033
clean table 32 2
fill table 32 2 to 1722181222
 10E:  DELTA: 0x3D063FFFE20A6000 1237BFB750ABC5D4 12  230(   1058325)0.000000000  12  530(   1057565)0.000000000  12  1f0(   1057502)0.000000000  12  130(   1040174)0.000000009  12  2f0(   1040192)0.000000010  12  930(   1056696)0.000000099  12  af0(   1056646)0.000000146  12  a30(   1040910)0.000002765
checking pair with DELTA: 0x80B2C00052319FFF 85F7EBD9A5CACFEE si0: 0xFE11F43F71412700 F6B7489194A2D4B7,0xE2AF29ED1B20D157 01C834D59668D06F si1: 0x7D5F343F1F0F8701 70BF5CB7EED804C9,0xD8493089E0552D49 D998F77D58F2D3C7
 1F4:  DELTA: 0x6FCE400052319FFF 85F7EBD9A5CACFEE -6    c(  67043292)0.000000000  -6   2c(  67161936)0.000043402
 3F4:  DELTA: 0x608E400052319FFF 85F7EBD9A5CACFEE 12   70(   1042089)0.009535608  12  f70(   1055012)0.014186071  12  3b0(   1042190)0.018029377
 2F4:  DELTA: 0xE82E400052319FFF 85F7EBD9A5CACFEE -6    4(  67198002)0.000000000  -6   24(  67032108)0.000000000  12  ec0(   1040797)0.000001182  -8   44(  16801938)0.003888811  -8   c4(  16801805)0.004755570  12  d0c(   1041987)0.004963123  12  6c0(   1054956)0.020123604  12  ac0(   1054907)0.027260483
  F4:  DELTA: 0xF76E400052319FFF 85F7EBD9A5CACFEE 12  800(   1056020)0.000015939
checking pair with DELTA: 0xB1E3C0007875E000 2C73576CA4DE67DE si0: 0xCB1F2D8DA9A5ACB8 079DA5BC62AB8EF8,0xF136A63903CFB057 99427D8A8F043A5D si1: 0x193B6D8D312FCCB7 DB2A4E4FBDCD271A,0x009C79F3B34D2CD3 22B43E5851BF9275
 1B4:  DELTA: 0x6B7C40007875E000 2C73576CA4DE67DE 14 2b00(    257580)0.000000000  14 1b00(    258140)0.000000760  14 3b00(    265893)0.000046023  14 1700(    258412)0.000046388  14  b00(    265785)0.000214713  14  700(    265705)0.000653519  14 3700(    265657)0.001259998  14 2700(    258731)0.004023711
checking pair with DELTA: 0x45728000B24DC000 1AFDFE5D4232E832 si0: 0x3456181E0244AE3D 9CFEF32202AB3CE3,0xC8CB61ECFAF163DF C41D4E73484C4E1D si1: 0xEEE3981D4FF6EE3D 8200F4C4C07854B1,0xDD8334AD194ECC83 F2A9D06A4F12C145
  46:  DELTA: 0x07CF4000B24DC000 1AFDFE5D4232E832 -6    c(  67065092)0.047214990
 146:  DELTA: 0xD5EF4000B24DC000 1AFDFE5D4232E832 14  700(    267561)0.000000000  14  b00(    267517)0.000000000  14 3700(    268055)0.000000000  14 3b00(    267320)0.000000000  12  700(   1065199)0.000000000  12  b00(   1065864)0.000000000  12  f00(   1031945)0.000000000  12  300(   1035611)0.000000000
 346:  DELTA: 0x722F4000B24DC000 1AFDFE5D4232E832 -6    4(  67216858)0.000000000  -6   24(  67010410)0.000000000  12  1c0(   1038151)0.000000000  12  2c0(   1038787)0.000000000  12  6c0(   1057954)0.000000000  12  5c0(   1057500)0.000000000  12  9c0(   1057053)0.000000006  12  ec0(   1040158)0.000000008

real	118m52,649s
user	2853m41,628s
sys	1m57,080s

A hypothetical example showing that this can be a real issue under the right/wrong circumstances

For research (in physics for example) 5 sigma is a requirement and that is for the experiment not for the PRNG so it would be unreasonable if the PRNG would consume more than 1% of that. If we start from where we left of, we have 115 bits in the seed to begin with, minus 32 as we will consume 2³² from each stream and minus 30 for the ~1% at 5 sigma. That leaves us with 53 bits in the seed, we now add 29 bits from the increment leaving us with 82 bits. These 82 bit would be expected to be affected by a collision if more than half are used (like in a birthday attack). That leaves us with being able to consume 2⁴¹ streams assuming they are perfectly randomly initialized. This compares to an ideal 2×128 bit seeded PRNG where we could consume 2⁹⁷ with the same 5 sigma and 2³² read constraints. How long would a supercomputer need to hit a correlated pair ? If we assume PCG-DXSM needs 10 CPU operations per output and we read 2³² per stream as in our code and a 1000 0000 Terra(fl)op/sec supercomputer is used. It would take about a day. 2⁴¹ * 2³² * 10 / ( 1000 0000 * 1000⁴ sec^-1 * 3600 sec/h * 24 h/day) = 1.09 … days The reader is here also reminded that we have not attempted to exploit the 2nd XOR in DXSM. Nor that the statistical tests used are very sophisticated. And that we are reading here 2³² values for each stream. A system favoring reading more on seemingly correlated sequences and less on others would need less data to run into problems

A workaround

The obvious one, is not to use PCG-DXSM with (increment based) streams. But if continued use of PCG-DXSM with streams is a goal, and if we assume the described issue here represents all the correlated streams (which certainly is not true as we ignored the 2nd XOR and likely have not found all correlation cases beyond that either and also only considered reasonable aligned streams, theres also other little details here and there I knowingly did not pay adequate attention to). Then one can construct increments instead of randomly in a systematic way so they always differ in bits that have been required to be identical in a collision. That can be achieved easily by using a counter fed through some bijective function for some extra pseudo randomness. The remaining bits could then still be set somewhat randomly. With that and 21 bits instead of 19 bits as in the attack removed (I have also found a collision with 2x21bits randomized) we have 127 – 63 – 2×21 = 22 bits left and thus ~4 million increments, given there are 2 odd values modulo 4 there are ~8 million non correlated streams of full 2¹²⁸ period (if we limit our self to what the implementation here can find) thus 2¹²⁸⁺²³. To clarify the differing bits we talk about are in the delta between aligned LCG outputs and not the increment values directly.

A solution

To solve this, first we need to understand why PCG has repeatedly been plagued by stream correlation issues, both the PCG “1.0” and now PCG 2.0 (DXSM). The reason appears to be because when using the increment and the seed and setting them randomly one inevitably challenges the mixer after the LCG with every constant difference. That is fundamentally very similar to feeding a mixer with a counter instead of a LCG. But the mixers seem designed to require more randomness than a counter provides.
The solution to this seems to be to give up on one of the assumptions leading to this, and these are 1. LCG, 2. random use of the increment, 3. a “simple” mixer.
Now if the simple mixer is replaced by a complex one than the LCG can be replaced by a counter more like in XSM64 because if the mixer is strong enough to work with a counter as input then the extra multiplication of the LCG no longer is useful and just slows it down.
I also do believe the solution is to spend more time analyzing the existing PRNGs instead of creating new ones. There are PRNGs that are fast and that have no known issues and seem to have received limited attention in terms of analyzing them. IMHO a new generator should only be created when its more optimal in some way than all other existing generators.

Final words

Iam curious if XSM64 has such issues too. From a quick glance it seemed designed with this sort of “correlation from offset” problem in mind, or at least i was too dumb to immediately produce a correlation the same way it works here. Sadly i did not have enough time to really investigate XSM64 so thats not meant as a recommendation, just a statement of myself being curious about …
I hope this whole blog entry is helpful to someone

More issues

After writing above, it came to my mind that as i already have the code to test for correlations between streams, it would be very easy to test this within the same period / LCG / stream / increment. After all we see correlations between streams that are misaligned by multiplies of 2¹⁰⁹ with different increments. So what about within teh same stream/increment? Testing streams of 2²⁶ length and misaligned by all the 65536 possibilities of the top 16 bits of the 128 bit. The 3 pairs tested found 13409, 15950 and 15360 correlations. I also tried a random subset of the top 32bit instead of 16 but these found no additional correlations with my quick tests. Retesting this with practrand to be more sure my tests are not all faulty. And practrand seems better in detecting these.

    STATET inc1 = 12345;
    STATET inc2 = inc1;
    STATET state1 = 31415;
    STATET state2 = step(state1, inc1, ((STATET)1)<<109);

    int64_t stream_length = 1LL<<60;
    for(int64_t i = 0; i< stream_length; i++) {
        OUTT v1, v2;
        v1 = pcg_dxsm(&state1, multiplier, inc1);
        v2 = pcg_dxsm(&state2, multiplier, inc2);

        v1 ^= v2;
        fwrite(&v1, 8, 1, stdout);
    }

step 1<<109
RNG_test using PractRand version 0.95
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

rng=RNG_stdin64, seed=unknown
length= 128 megabytes (2^27 bytes), time= 3.6 seconds
  no anomalies in 196 test result(s)

rng=RNG_stdin64, seed=unknown
length= 256 megabytes (2^28 bytes), time= 8.4 seconds
  no anomalies in 213 test result(s)

rng=RNG_stdin64, seed=unknown
length= 512 megabytes (2^29 bytes), time= 16.3 seconds
  no anomalies in 229 test result(s)

rng=RNG_stdin64, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 29.9 seconds
  no anomalies in 246 test result(s)

rng=RNG_stdin64, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 52.3 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:cross                 R=  +4.9  p =  1.8e-4   unusual
  ...and 262 test result(s) without anomalies

rng=RNG_stdin64, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 94.4 seconds
  no anomalies in 279 test result(s)

rng=RNG_stdin64, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 179 seconds
  no anomalies in 295 test result(s)

rng=RNG_stdin64, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 342 seconds
  no anomalies in 311 test result(s)

rng=RNG_stdin64, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 663 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low16/64]FPF-14+6/16:all         R=  -5.9  p =1-2.3e-5   mildly suspicious
  ...and 324 test result(s) without anomalies

rng=RNG_stdin64, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 1298 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(15,14-3)             R=  +8.7  p =  2.3e-7   mildly suspicious
  FPF-14+6/16:all                   R=  +5.6  p =  1.0e-4   unusual
  TMFn(2+6):wl                      R= +25.9  p~=   1e-8    very suspicious
  [Low16/64]TMFn(2+4):wl            R= +28.2  p~=   7e-10   very suspicious
  [Low4/64]TMFn(2+2):wl             R= +25.1  p~=   3e-8    suspicious
  ...and 335 test result(s) without anomalies

rng=RNG_stdin64, seed=unknown
length= 128 gigabytes (2^37 bytes), time= 2268 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(15,14-2)             R= +15.2  p =  4.3e-13   VERY SUSPICIOUS 
  FPF-14+6/16:all                   R= +10.3  p =  3.9e-9    VERY SUSPICIOUS 
  TMFn(2+6):wl                      R= +58.1  p~=   7e-28     FAIL !!        
  TMFn(2+7):wl                      R= +35.3  p~=   3e-14     FAIL           
  TMFn(2+8):wl                      R= +29.8  p~=   7e-11    VERY SUSPICIOUS 
  [Low16/64]FPF-14+6/16:cross       R=  +5.8  p =  3.2e-5   mildly suspicious
  [Low16/64]TMFn(2+4):wl            R= +58.1  p~=   6e-28     FAIL !!        
  [Low16/64]TMFn(2+5):wl            R= +36.2  p~=   1e-14     FAIL           
  [Low16/64]TMFn(2+6):wl            R= +31.1  p~=   1e-11    VERY SUSPICIOUS 
  [Low16/64]TMFn(2+7):wl            R= +19.3  p~=   1e-5    unusual          
  [Low4/64]TMFn(2+2):wl             R= +59.6  p~=   9e-29     FAIL !!        
  [Low4/64]TMFn(2+3):wl             R= +34.9  p~=   6e-14     FAIL           
  [Low4/64]TMFn(2+4):wl             R= +31.0  p~=   1e-11    VERY SUSPICIOUS 
  ...and 342 test result(s) without anomalies


step 1<<110
RNG_test using PractRand version 0.95
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

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

rng=RNG_stdin64, seed=unknown
length= 256 megabytes (2^28 bytes), time= 6.5 seconds
  no anomalies in 213 test result(s)

rng=RNG_stdin64, seed=unknown
length= 512 megabytes (2^29 bytes), time= 14.6 seconds
  no anomalies in 229 test result(s)

rng=RNG_stdin64, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 26.1 seconds
  no anomalies in 246 test result(s)

rng=RNG_stdin64, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 49.2 seconds
  no anomalies in 263 test result(s)

rng=RNG_stdin64, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 94.8 seconds
  no anomalies in 279 test result(s)

rng=RNG_stdin64, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 180 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(16,14-6)             R=  +7.8  p =  5.1e-6   unusual
  ...and 294 test result(s) without anomalies

rng=RNG_stdin64, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 325 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(16,14-5)             R= +12.5  p =  3.4e-10  very suspicious
  [Low16/64]FPF-14+6/16:all         R=  +4.9  p =  4.5e-4   unusual
  ...and 309 test result(s) without anomalies

rng=RNG_stdin64, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 599 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(16,14-5)             R= +25.2  p =  8.7e-21    FAIL !
  ...and 324 test result(s) without anomalies


step 1<<111
RNG_test using PractRand version 0.95
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

rng=RNG_stdin64, seed=unknown
length= 128 megabytes (2^27 bytes), time= 2.6 seconds
  no anomalies in 196 test result(s)

rng=RNG_stdin64, seed=unknown
length= 256 megabytes (2^28 bytes), time= 7.7 seconds
  no anomalies in 213 test result(s)

rng=RNG_stdin64, seed=unknown
length= 512 megabytes (2^29 bytes), time= 15.1 seconds
  no anomalies in 229 test result(s)

rng=RNG_stdin64, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 28.4 seconds
  no anomalies in 246 test result(s)

rng=RNG_stdin64, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 52.3 seconds
  no anomalies in 263 test result(s)

rng=RNG_stdin64, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 92.2 seconds
  no anomalies in 279 test result(s)

rng=RNG_stdin64, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 172 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(17,14-7)             R=  +9.1  p =  4.5e-7   mildly suspicious
  [Low16/64]FPF-14+6/16:cross       R=  +7.8  p =  6.4e-7   suspicious
  ...and 293 test result(s) without anomalies

rng=RNG_stdin64, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 337 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(17,14-6)             R= +16.4  p =  1.4e-12   VERY SUSPICIOUS
  FPF-14+6/16:(20,14-8)             R= +16.1  p =  1.1e-11   VERY SUSPICIOUS
  FPF-14+6/16:cross                 R=  +6.5  p =  8.5e-6   mildly suspicious
  [Low16/64]FPF-14+6/16:cross       R= +18.2  p =  1.2e-15    FAIL !
  ...and 307 test result(s) without anomalies


step 1<<112
RNG_test using PractRand version 0.95
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

rng=RNG_stdin64, seed=unknown
length= 128 megabytes (2^27 bytes), time= 2.8 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:cross                 R=  +7.9  p =  5.5e-7   suspicious
  ...and 195 test result(s) without anomalies

rng=RNG_stdin64, seed=unknown
length= 256 megabytes (2^28 bytes), time= 7.9 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:cross                 R= +16.0  p =  7.3e-14    FAIL
  ...and 212 test result(s) without anomalies


step 1<<115
RNG_test using PractRand version 0.95
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

rng=RNG_stdin64, seed=unknown
length= 128 megabytes (2^27 bytes), time= 2.9 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:cross                 R= +67.0  p =  9.4e-57    FAIL !!!!
  TMFn(2+0):wl                      R= +23.5  p~=   1e-7    suspicious
  [Low16/64]FPF-14+6/16:(4,14-3)    R= +13.9  p =  6.3e-12   VERY SUSPICIOUS
  [Low16/64]FPF-14+6/16:(5,14-4)    R=  +8.1  p =  1.4e-6   unusual
  [Low16/64]FPF-14+6/16:all         R=  +6.4  p =  1.5e-5   mildly suspicious
  [Low16/64]FPF-14+6/16:cross       R=  +6.5  p =  1.3e-5   mildly suspicious
  ...and 190 test result(s) without anomalies


step 1<<120
RNG_test using PractRand version 0.95
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

rng=RNG_stdin64, seed=unknown
length= 128 megabytes (2^27 bytes), time= 2.6 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(2+13,13-9,T)                 R= +26.0  p =  5.7e-7   mildly suspicious
  Gap-16:A                          R=  +6.9  p =  2.5e-5   mildly suspicious
  FPF-14+6/16:(0,14-0)              R=  +7.5  p =  1.6e-6   unusual
  FPF-14+6/16:(1,14-0)              R= +18.0  p =  2.8e-16    FAIL
  FPF-14+6/16:(2,14-0)              R= +16.0  p =  1.8e-14    FAIL
  FPF-14+6/16:(3,14-1)              R= +18.7  p =  2.4e-16    FAIL
  FPF-14+6/16:(4,14-2)              R=  +7.5  p =  2.2e-6   unusual
  FPF-14+6/16:(5,14-2)              R= +10.7  p =  3.7e-9   very suspicious
  FPF-14+6/16:(6,14-3)              R= +10.7  p =  3.8e-9   very suspicious
  FPF-14+6/16:(7,14-4)              R= +25.3  p =  1.4e-20    FAIL !
  FPF-14+6/16:all                   R= +94.7  p =  2.4e-88    FAIL !!!!!
  FPF-14+6/16:cross                 R= +2465  p =  3e-2074    FAIL !!!!!!!!
  TMFn(2+0):wl                      R=+968.3  p~=   6e-576    FAIL !!!!!!!
  TMFn(2+1):wl                      R=+487.2  p~=   2e-286    FAIL !!!!!!
  TMFn(2+2):wl                      R=+232.7  p~=   5e-133    FAIL !!!!!
  [Low16/64]BCFN(2+1,13-4,T)        R= +10.9  p =  1.0e-4   unusual


step 1<<127
RNG_test using PractRand version 0.95
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

rng=RNG_stdin64, seed=unknown
length= 128 megabytes (2^27 bytes), time= 2.5 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(2+0,13-3,T)                  R=+24986  p = 0           FAIL !!!!!!!!
  BCFN(2+1,13-3,T)                  R=+24275  p = 0           FAIL !!!!!!!!
  BCFN(2+2,13-3,T)                  R=+24133  p = 0           FAIL !!!!!!!!
  BCFN(2+3,13-3,T)                  R=+23873  p = 0           FAIL !!!!!!!!
  BCFN(2+4,13-4,T)                  R=+30456  p = 0           FAIL !!!!!!!!
  BCFN(2+5,13-5,T)                  R=+37691  p = 0           FAIL !!!!!!!!
  BCFN(2+6,13-5,T)                  R=+36654  p = 0           FAIL !!!!!!!!
  BCFN(2+7,13-6,T)                  R=+43148  p = 0           FAIL !!!!!!!!
  BCFN(2+8,13-6,T)                  R=+39020  p = 0           FAIL !!!!!!!!
  BCFN(2+9,13-7,T)                  R=+39135  p = 0           FAIL !!!!!!!!
  BCFN(2+10,13-8,T)                 R=+33354  p =  8e-8466    FAIL !!!!!!!!
  BCFN(2+11,13-8,T)                 R=+19688  p =  1e-4997    FAIL !!!!!!!!
  BCFN(2+12,13-9,T)                 R=+11650  p =  7e-2619    FAIL !!!!!!!!
  BCFN(2+13,13-9,T)                 R= +5830  p =  3e-1311    FAIL !!!!!!!!
  DC6-9x1Bytes-1                    R= +2564  p =  1e-1574    FAIL !!!!!!!!
  Gap-16:A                          R=+362.0  p =  3.5e-308   FAIL !!!!!!
  Gap-16:B                          R=+576.2  p =  2.4e-461   FAIL !!!!!!!
  FPF-14+6/16:(2,14-0)              R=+663.1  p =  2.7e-613   FAIL !!!!!!!
...

Correlations based on the lower half of the LCG

Lets try picking some correlated combinations with (using my very simple pcg-dxsm implementation)

Besides the exactly equal ones, the more careful reader will have noticed that each line either has even or odd entries, so the 3 seed/increment pairs generate equal results in the lowest bit.

You might ask why does this all happen? Well, the identical numbers happen because the lowest bit is ored away in DXSM, that is forced to be 1. So any cases differing only by that bit at the LCG stage become identical in later stages. The other similarities happen because the mixing isnt as good as it needs to be to remove all differences from very similar input and LCGs can produce such very similar input when one picks the “wrong” parameters.

Did i hand pick the worst ? Is that the only case ?
lets see

Here 7 out of 8 bytes match apparently for each. Is that the worst ? no we could make part of the first byte match too, it just becomes harder to color the table to match that.

Correlations based on the upper half of the LCG

Update 2024-03-02, After thynson noticed that the above 2 classes of correlations, all have multiplier-1 as a coresidual of the increment. Ive looked more and found more classes of correlations.
The above 2 cases produce correlations because they introduce 2 specific classes of differences in the lower half of the underlying LCG, we can also introduce other specific differences in the upper half to create correlations. I first thought the mixing stage would make this difficult, but it doesnt seem that difficult.

Above attacks the first stage of the mixer, we can also attack the 2nd stage, it looks less impressive but none the less instead of 1 identical byte in 256 we see alot more

We can also use this to generate more than 8bit matches, but they are spread out more so it doesnt show up nicely in the first 30 output values.
For example ./pcg-dxsm-64 15750249268501108917 164824157741578258584156320684186520853 3046549733826659956002159287 1000000 16 and ./pcg-dxsm-64 15750249268501108917 123456789 31415 1000000 16 produce a million values, we expect the low 20 bits to match in one case in a million on average but these have over a thousand such matches

Update 2024-03-03: Verifying that our PCG64-DXSM implementation is correct

./pcg-dxsm-64  15750249268501108917 123456789 31415 10 10
 6213575192384761538
  453844501346797651
 5127139872326394501
 2829747299987210688
 6941700003234024114
  422759593322230831
15541880859405869675
 3179485701156339734
17141404421690271452
12708873539510705095

python3
from randomgen import PCG64
g = PCG64(2**128+31415-123456789,123456788/2,variant="dxsm",mode="legacy"); 
for i in range(10): print(g.random_raw())
6213575192384761538
453844501346797651
5127139872326394501
2829747299987210688
6941700003234024114
422759593322230831
15541880859405869675
3179485701156339734
17141404421690271452
12708873539510705095

Update 2024-03-04: Add correlations with equal seeds

Correlations with equal seeds

For the case of equal seeds it must be first said that different pcg64-dxsm implementations mangle the seed in different ways. Thus whats equal in one is not equal in another. We show examples of equal seeds at the LCG level first, this is how the previous examples defined the seed.

And another example:

Now python randomgen + numpy

from randomgen import PCG64
g = PCG64(31415,(310562926860152171542224643668532814649>>1),variant="dxsm",mode="legacy"); g2 = PCG64(31415,(310562926860152171526474394400031705733>>1),variant="dxsm",mode="legacy");
for i in range(30): print("0x" + format(g.random_raw(), "016X") + " 0x" + format(g2.random_raw(), "016X"))

g = PCG64(31415,(328721727944725361000316204835460899641>>1),variant="dxsm",mode="legacy"); g2 = PCG64(31415,(310562926860152171527627315904638552709>>1),variant="dxsm",mode="legacy");
for i in range(30): print("0x" + format(g.random_raw(), "016X") + " 0x" + format(g2.random_raw(), "016X"))

An example of the upper part of the LCG in PCG64-DXSM being modified with identical seed in numpy/randomgen

g = PCG64(31415,(292528383318202715988945170563770901305>>1),variant="dxsm",mode="legacy"); g2 = PCG64(31415,(140421743439297021051919259480919575173>>1),variant="dxsm",mode="legacy");
for i in range(30): print("0x" + format(g.random_raw(), "016X") + " 0x" + format(g2.random_raw(), "016X"))

All PCG implementations seem to allow more or less easy computation of the seed, but a new PCG implementation has appeared in 2019 or so.
PCG-DXSM, the source code tells us “This is a new, more powerful output permutation” and “This latter aspect means that the scrambling applied to the high bits depends on the low bits, and makes it (to my eye) impractical to back out the permutation without having the low-order bits.”
Ok. lets try
Heres for reference, what this is about:
multiplier is a odd 64bit constant, SHR1 is half the state bits, SHR2 is quarter the state bits and SHR3 is 3 eights of the state so 64, 32, 48 for the 128/64 bit variant and 32, 16, 24 for the 64/32bit one. inc is forced to be odd too.

    state = state * multiplier + inc;

    l1 = state | 1;
    h1 = state >> SHR1;
    h2 = h1 ^ (h1 >> SHR2);
    h3 = h2 * multiplier;
    h4 = h3 ^ (h3 >> SHR3);
    return h4 * l1;

l1 is forced to be odd as we can see, so what do we know if pcg_dxsm returns 0 ? When is X * (2Y+1) = 0 ? Yes when X is 0 so h4 has to be 0 (yes i jump over some details of rings) and what can h3 be ? only 0, and h2 ? again only 0 and h1 ? yes its 0.
So when pcg_dxsm() return 0 you just learned half its internal state.
This can be extended a bit, for example when it returns a odd number h4 must be odd, when it returns a number that contains a factor of 2^x then so must h4.

Can we compute the seed and increment from this ? I did not try, but i think so.
Just consider this: we decide how many bits we want to look for in the data and we brute force the rest. (there quite possibly could be an easier way, thats just the obvious one)
if we want 16bits to be from the data we would look for about 100k output data values, look for the values that are multiplies of 65536, these points would have h4 a multiple of 65536 and thus the low 17bits of h4 would be known. If we now brutefoce the 32-17 that is 15 low bits of the state and increment, these together fully determine, first all the low 15bits of all states and together with that the cases where we know the low 17 bits of h4 we now can invert the multiply and find the rest of h4. For each known h4 its trivial to find the upper half of the state. And the rest is identical to finding the state and increment of a truncated LCG and after the upper bits are found the lower can be trivially found from the h4*l1.
As i have not implemented this it is very possible that i have missed something or made some mistake.

Btw i think PCG and other PRNGs are really great little math exercises. They are also good PRNGs as long as one understands their limitations.

As ive looked at many PRNGs in the last few days, heres a quick list/note about which seem good.
To be on this list they must be

• Fast
• Fail 0 general statistical tests
• 64bit output
• minimum period of at least ~2⁶⁴

I tried a bit to create a list of diverse types of generators. If i hear about any of these generators failing some tests, i will remove them (unless i forget), i also may add more in case i see others in the future. The list is in alphabetical order. None of the generators is secure, and i expect that the state can be found from the output with little effort for every fast PRNG. Some of these generators allow efficient seeking. For others I do not know how to efficiently seek.
Also see https://pracrand.sourceforge.net/RNG_engines.txt, https://prng.di.unimi.it/,

This omits basic LCGs, LFGs, LFSRs as well as simple variants of these because they fail tests. PRNGs which are similar to the listed ones but worse in one way and equivalent in all others are omitted too. Cryptographic PRNGs are omitted because they are slow.

SFC64 and XSM64 are testet here The others in the table ive tested with practrand to 32TB:
mwc256_test,
splitmix64_test,
xoroshiro128starstar_test
also several of them have been tested here,

As i was looking for the best PRNG ;) i found SFC64, its fast, seems to pass all tests, and it was fun to find a way to compute the seed from a few output values.
But the more one looks the more one finds, there are many other great PRNGs. I would stay away from hyped up generators, like the mersene twister was in the distant past.

Now about SFC64, heres a simple implementation. It can also compute values backward.

And for fun, heres an implementation that will turn 10+ values back into the 3 seeds and counter used to create them.
The way this works is that first we guess the 16-19 MSB of the a or b register. Next we assume that the corresponding MSB of the counter are 0. Because its 64bits, thats reasonable and pretty difficult to be otherwise. From this and a = b ^ (b >> 11) and tmp = a +b + counter++; we can estimate teh MSBs of the future and past a and b registers (they slowly become less exact due to the counter but thats insignificant over the distance we need them)
For the 8 rotation states we then invert b = c + (c << 3); for the MSBs we have (which has 9 solutions and iterating over them gives us 3 extra bits knowledge of c). The 8 rotation states are iterated over in 2 forward steps of 3 followed by a backward step of 5. This way we minimize the distance we move away from the start point which limits effects of the unknown LSBs and also limits the needed amount of data. In addition the 3,3,-5 pattern splits the previously determined part of the c register so that the lower part of the MSB becomes shifted into the MSB. This allows us to check the lower part of our data from the c register together with the MSB of the b register at that point and the known output data. This is crucial to limit the otherwise exponential increase of computations with each part of c that is iterated over. Towards the end of the c register, we then compute the a,b and counter from it and the known output and if it matches, backstep to counter =1 to output the seed at the start. It would also be possible to use a heuristic in guessing the initial a/b values, so as to not search the 17-19 bit space but it seems the bad ones get rejected naturally quickly so this lead to little gain and its already quite fast.
I do realize after writing above that this description is probably hard to understand. I should expand this and draw diagramms, but ATM i have no time so please read the source :)

Example: of finding the seeds after 1000 rounds

./sfc64 0x123456785 0x978653 0xCCAADDEE0F 1000 30 16 
0x8A9912C022EA7402
0x26971AE36A1CEACA
0x97B4CF575274B9F4
0xC9212C12EEE58E49
0x9B45979745BB2E20
0x857B5EEB83507D6D
0x243E719FF5356874
0xE6EB4E22DDDEDCA6
0xAF0DC4AF0234A763
0x9946B8BD21C71BE9
0x14D42990A607161B
0x66A19FF0771F930C
0xE3E580CA96D08FD3
0xDAED73C40D44E397
0x90A0E96731283123
0x183075440F78DA33
0xE46ACCC1AECD9C6C
0x1CA82D6053C47933
0xC707C633E34377CA
0xF60FC6DB95DE2631
0x0B2342552B1B4912
0xC32F27E766B148FD
0x055FDF9DC44345CF
0xADFD892D38628512
0x5AA6881F0C6E3ADE
0x72FD99BE0899B07C
0x6F31D2773AB970F6
0xC07850CC6EFD7868
0x5EC7E6C020A407CA
0xF048FCEDEA87BE0A


time ./sfc64-breach  0x8A9912C022EA7402 0x26971AE36A1CEACA 0x97B4CF575274B9F4 0xC9212C12EEE58E49 0x9B45979745BB2E20 0x857B5EEB83507D6D  0x243E719FF5356874 0xE6EB4E22DDDEDCA6 0xAF0DC4AF0234A763 0x9946B8BD21C71BE9 0x14D42990A607161B 0x66A19FF0771F930C 0xE3E580CA96D08FD3 0xDAED73C40D44E397 0x90A0E96731283123  0x183075440F78DA33 0xE46ACCC1AECD9C6C 0x1CA82D6053C47933 0xC707C633E34377CA 0xF60FC6DB95DE2631 0x0B2342552B1B4912 0xC32F27E766B148FD 0x055FDF9DC44345CF 0xADFD892D38628512 0x5AA6881F0C6E3ADE 0x72FD99BE0899B07C 0x6F31D2773AB970F6 0xC07850CC6EFD7868 0x5EC7E6C020A407CA 0xF048FCEDEA87BE0A
attempt 0
Found (a=0x0000000123456785 b=0x0000000000978653 c=0x000000CCAADDEE0F counter=0x0000000000000001 original_counter=1002
step 5121675

real	0m0.083s
user	0m0.071s
sys	0m0.012s

For plain LCG the problem is trivial and an implementation shown in my last post. PCG falls in 2 categories, the PCG-XSL-RR which is based on an LCG, this was solved in the Paper by Bouillaguet, Martinez and Sauvage.
The remaining PCG generators are different and simpler, they are based on an truncated LCG. The problem of finding an increment and seed is marginally harder as it is for the corresponding truncated LCG. It can be done using Lattice reduction (even some half bastardized version seems to work). The problem and the surprise for me really is that the solution in general is not unique. I guess it was a surprise after reading in the original PCG paper how additional random streams can be created by changing the increment. This is really not true. Changing the increment does not really produce “different” random data, it just offsets it.

Let me first show an example with a plain LCG (using the multiplier 6364136223846793005 from PCG with 64bit state)

This is not a odd exception, no, for every choosen LCG and choosen offset (here it is +1) theres a seed and increment that will produce a offset sequence of random numbers.
You can use lcg-breach to find them by just asking it to find parameters for a modified sequence.
Now thats LCGs, What about truncated LCGs ? its worse because they discard the low bits. You get sequences that can be exactly equal for MANY values even with different increment and seed. And that is what the problem is in determining the increment for truncated LCGs and the corresponding PCGs. For PCG-XSL-RR the low LCG bits are XORed in so there remains a effect on the output and its possible to determine the increment but for 128/64 and 64/32 PCG-XSH-RR the low bits of the state do not affect the output as long as their effect stays limited to these low 27bit (for 64/32 bit) in future states they cannot be computed from the output. Or in other words the output from 2 PCG-XSH-RR with differing increments can be identical for a long time.

On top of that, there is also a set of seed,increment pairs that produce constant output.
consider this:

LCG         : out[i+1] = out[i] * m + a mod n
what we want: C        = C      * m + a mod n

just solve it:

C - C * m = a mod n

choose the constant C you want and this will tell you the increment a that will keep the generator at that constant when its started on it.

and how do we now create a offseted LCG ?
simply add it with the constant above

out[i+1]     =  out[i]      * m + A     mod n
           C =           C  * m +     a mod n
out[i+1] + C = (out[i] + C) * m + A + a mod n

And yes LCGs of the same multipler and modulo seem to form an abelian group with addition.

Just for fun, heres a program to generate random numbers using a Linear Congruential Generator from a specified multiplier, increment, seed and number of bits.
And a second one that will tell you the multiplier, increment, seed for a given 3 output numbers from above.

Have fun encrypting important messages


./lcg 64 6364136223846793005 1442695040888963407 314159 5
1758213515780721042
8369501526408240633
14286244372924288276
12908628925188209107
17643264774698309734

$ ./lcg-breach 64 1758213515780721042 8369501526408240633 14286244372924288276
Seed: 314159 0x000000000004CB2F
Multiplier: 6364136223846793005 0x5851F42D4C957F2D
Increment: 1442695040888963407 0x14057B7EF767814F


How did this start ? Someone found a bug or 2 in the libavutil/eval.c random(), so i proposed a patch replacing it by Marsaglias 64-bit KISS PRNG. Nicklas Haas then ask me why iam not using PCG yesterday. And i didnt know really what PCG is :) so i looked found the paper found a wegpage that was down the exact day i tried to look at it (yeah its up again now). And a wikipedia page taking about “It has been shown that it is practically possible (with a large computation) to recover the seed of the pseudo-random generator given 512 consecutive output bytes.”. That triggered me a bit ;)

The paper about PCG is 58 Pages so reading that is not an option. But we skim it and look at the pretty pictures, theres one that marks several PCG variants as insecure. Luckily the one listed at wikipedia (PCG-XSH-RR is not marked as insecure) In fact there are 2 PCG-XSH-RR, one with 64bit state and 32bit output and one with 128bit state and 64bit output. So i tried them. Theres also a paper about breaking PCG-XSL-RR which differs by some shifts it seems from XSH. That paper talks about also recovering the increment and that for that it needs “512 bytes of challenge input;in the worst case, the process takes 20 000 CPU hours” ugh, i dont have that. Luckily we know the increment as its not a variable in the implementation and with that, the paper tells us “breaking XSL-RR needs 23 core minutes”. But we took XSH-RR because it was on wikipedia :) and the original paper also recommends it

6.3.1 32-bit Output, 64-bit State: PCG-XSH-RR
Here the design goal is to be a good all-purpose random number generator. The intent
is to balance speed with statistical performance and reasonable security, charting a
middle-of-the-road path. (It’s the generator that I recommend for most users.)”

So we are not totally wasting our time but we can have fun exercising breaking a “not insecure” PRNG with “reasonable security”.

A few hours later, am i lucky ? am i smart ? or is the PCG-XSH-RR a insecure generator, i dont know, I think i maybe picked the easier one but still. These following need 3-4 output values from the PCG-XSH-RR to find and verify its state, from which all future and past output can be computed.
For the 64/32bit variant we compute all tables at runtime, for the 128/64 variant we hardcode the 152 entry table needed as it needs a few minutes to be computed. But the table doesnt depend on the seed nor on the increment, just a new multiplier would need a new table.
The actual execution for both including loading the program, generating the random numbers finding the seed again and printing it all together takes less than 100ms
Code is here


time ./pcg-xsh-rr-64-32-breach $((0x1234578ACDEF11))
INV 0xC097EF87329E28A5 0x1 gcd=0x1
Seed = 0x1234578ACDEF11
PCG output 0 = 0x90DA0D79
PCG output 1 = 0xCF0EAEE6
PCG output 2 = 0x423D36BE
PCG output 3 = 0xAE152565
PCG output 4 = 0x2C48B4D4
PCG output 5 = 0x9EE6CC50
PCG output 6 = 0x903FC56A
PCG output 7 = 0xC85B3AED
PCG output 8 = 0x87B29579
PCG output 9 = 0xA486F671
Table 0 0x00000000000000005851F42D4C957F2D 0x0000000000000001
Table 1 0x000000000000000008F5DC87E5C07D87 0x0000000000000003
Table 2 0x00000000000000000148A921ACEF6819 0x000000000000001D
Table 3 0x00000000000000000006C363D4CB5B28 0x00000000000000C8
Table 4 0x00000000000000000002BCFA0DFD0A8F 0x000000000000262B
Table 5 0x00000000000000000001738A552BC485 0x00000000000071B9
Table 6 0x000000000000000000002A1A9C5A7E7B 0x000000000000BD47
Table 7 0x0000000000000000000007652A02ADCE 0x00000000000635C6
Table 8 0x0000000000000000000002445FB59459 0x000000000024855D
Table 9 0x0000000000000000000001AC54D3A396 0x00000000008BDFAE
Table 10 0x00000000000000000000011449F1B2D3 0x0000000000F339FF
Table 11 0x00000000000000000000007C3F0FC210 0x00000000015A9450
Table 12 0x000000000000000000000060733D935D 0x00000000031C82F1
Table 13 0x000000000000000000000044A76B64AA 0x0000000004DE7192
Table 14 0x000000000000000000000028DB9935F7 0x0000000006A06033
Breaching spin:.........................................................................................................................................................................................................................................................................................................................
Candidate 0x48EAFC5649EE9492 for 90DA0D79 CF0EAEE6 423D36BE
found Seed = 0x1234578ACDEF11

And the PCG-XSH-RR-128/64 one:

time ./pcg-xsh-rr-128-64-breach $((0x1234578ACDEF11))
INV 0x98ABC8B0716EAC8D 0x1 gcd=0x1
Seed = 0x1234578ACDEF11
PCG output 0 = 0xE49F66304A892198
PCG output 1 = 0x58C80AA8C2F10A26
PCG output 2 = 0xD2B380859B808368
PCG output 3 = 0x60715FDB8EE68956
PCG output 4 = 0xB0D0AAF3073F2EDA
PCG output 5 = 0xC5876DE56C99EDB3
PCG output 6 = 0x68371CCDC061F3D
PCG output 7 = 0x7118EC9199028ED5
PCG output 8 = 0xAC0DAAF55D9A009C
PCG output 9 = 0x709AD75080EDE32E

real 0m0.089s
user 0m0.069s
sys 0m0.020s


Maybe its a great PRNG, i dont know i did not look at that aspect, but its not secure if i can break it after a few hours work :)

After the little bit of analysing PRNGs in the last blog post, which PRNGs exactly seem good?

Fastest PRNGs

If one either needs a very fast PRNG or one has some means to easily test that the output is good enough (like looking to see if a noise filter produces no vissible aritifacts) then folllowing could be considered.
Linear congruential generators, Additative lagged fibbonacci generators or even just an array of random numbers that gets used repeatedly, …
Each of these has its serious flaws, LCGs have very poorly performing LSBs, that is the lowest n bits never have a period larger than 2ⁿ. ALFGs contain number triplets (the ones spaced like the taps used in the PRNG) that when used as coordinates in a cube would all fall in a single plane. Still these generators are often good enough, and have been used for a long time and are widespread, that is all C libs ive seen use either of them for rand() for examle.

Good and fast PRNGs

If one wants a generator free of big flaws and that is still reasonably fast then the number of choices goes down, first there is
4 tap additative LFG (x_i = x_i-55 + x_i-119 + x_i-179 + x_i-256 mod 2ⁿ) this one passed all of testu01 but has a obvious linear dependancy between its values.
Combined generators, these generators combine the output of several simple generators and generally pass all tests, many of them though are slow like CLCG4 which combines 4 LCGs, combined generators like f_i = g_i + h_i also have the flaw that f_i – f_i+p = h_i – h_i+p when p is the period of g. This also means that f_i – f_i+p – (f_i+q – f_i+p+q) = 0 when p and q are the periods of h and g. Thus all combined generators which are made of constituent generators with “bruteforceable periods” are cryptographically likely very weak. A combined generator that is reasonable fast is KISS99.
Multiplicative lagged fibonacci generators, like for example (x_i = x_i-55 * x_i-24 mod 2ⁿ) these generators also tend to pass all tests as long as only the most significant bits are used, that is for example the top 32 bit of a 64 bit generator. The least significant bit of such a generator is always 1, its next bit behaves like a LFSR identically to the least significant of an additative or xor based LFG. One trick to get rid of the least significant bit without ending up with just 31 or 63 bits is to use 2*a*b+a+b instead of a*b, this works because a and b are (have to be) odd in a normal MLFG and (2*A+1)(2*B+1) = 4AB + 2A + 2B + 1

Best but slow PRNGs

“Anything” based on AES, SHA-1, MD5, …

Bad PRNGs

These are PRNGs that are both slower and worse in terms of their output than others, examples are
Mersene twister, becuase its output is purely based on the XOR of previous bits thus being not nearly as good as some pretend it to be while it also isnt nearly as fast compared to other properly implemented PRNGs.
Combined generators with lots of modulo by non power of 2, these are slow …
Weak generators from which many output values are thrown away, again these are slow …

I guess most developers have once or more than once run into the question of, “which PRNG should one use”. The awnser, or more precissely my awnser to this, would be it really depends on for what one plans to use it.
There is no perfect generator, there are fast ones, and there are good ones, but the best arent the fastest. One has to choose depending on ones needs

• If one wants to generate white noise for a human listener then the best generator simply is the fastest that produces perfectly sounding white noise, it really doesnt matter if it has some statistical defects or not.
• If one wants to use the random numbers for cryptographic purposes, a perfect generator that has been extensively tested and no flaws found is needed.
• If one wants to test a scientific theory by simulation, one needs a generator that doesnt cause a wrong result from the simulation, but as the correct result isnt known, one cant easily pick based on this criteria. Thus one has little alternative to picking a generator that has few statistical defects and is fast enough for the amount of numbers needed. Or better even run the simulation 2-3 times with very different generators

So which generators are there and what defects do they have? This actually is rather easy to awnser, or then maybe not ;) well, there is George Marsaglias Diehard and Pierre L’Ecuyers
TestU01 both contain code to test PRNGs, later also contains a paper describing the results of these tests for most recent and popular PRNGs.

In an ideal world one would just have to look at the TestU01 paper And pick a generator that has the amount of defects and speed one wants. At least thats what i thought before testing a few generators myself, more precissely i took a few of the generators that passed all tests in TestU01 and run 2 (to me obvious) tests against them

1. Use a gaussian like algorithm to find out if any bits in the output are just a linear (mod 2) combination of previous output bits
2. Use a gaussian like algorithm to find out if any scalars in the output are just a linear (mod maxoutput+1) combination of previous output scalars
3. Use a gaussian like algorithm to find out if any bits (only considering the least significant of each scalar) in the output are just a linear (mod 2) combination of previous such output bits

The first 2 of these tests in the way i implemented them only consider outputs surrounding a scalar with 20 zero LSBs, though as far as i tested it this 20bit trick only made a difference for the additative LFG with only the 32MSB used, but i did not test all without this 20bit check

Failing either of these tests makes the PRNG at least unsuitable for linear algebra under the same modulo, so its certainly a statistical defect. All linear congruential generators have to fail at least the test that works in their own modulo, after all they are linear, but actually all i tested failed both tests. Lagged fibonacci generators based on addition or xor similarly must fail and do. All multiplicative Lagged fibonacci generators fail as well due to linear dependancies in their lower bits. All linear feedback shift register based generators like the mersene twister very obviously have to fail too, i did not test any of them though as none passed TestU01.

The actual generators that passed TestU01 and failed mine where:
superduper64, Marsa-lfib4, DX-47-3, MRGk5_93, Lfib(2^64,55,24,*), brent-xor4096s

The actual generators that passed TestU01 and passed mine where:
brent-xor4096s, MRG31k3p, CombMRG96, ran2, CLCG4, KISS99

Note1, there are more generators that passed TestU01 but i did not test them

Note2, The first 2 tests where only searching for linear dependancies within 512 consecutive scalars, that is 32kbit for a 64bit PRNG, the 3rd test was considering 32kbit of LSBs

In addition to that, limiting the output to just 32MSB of 64 made the multiplicative LFG 2^64,55,24,* pass mine while the same trick with a additative one was not helping, KISS99 also passed when SHR3 or CONG was droped but not when both or MWC alone was droped

No source code this time though because i randomly copied PRNGs from various places, but if there is interrest i could throw all but my own code out and post that

To be continued when iam less tired … ;)