r/RNG 15h ago

Probably the oldest generator (from 1973) that passes BigCrush

11 Upvotes

It seems that I've managed to find the high-quality non-cryptographic PRNG that is older than DES. It was designed by A. Grube in 1973 and belongs to the MRG (multiple recursive generators) family. It is based on the next recurrent formula:

x_i = 518175991 x_{i-1} + 510332243 x_{i-2} + 71324449 x_{i-3} mod (2^{31} - 1)

Its period is approximately 2**93, initializers should be between 1 and 2**31 - 2. I've checked the coefficients using galois Python package, they seem to be correct, i.e. give a full period. It passes SmallCrush, Crush and BigCrush batteries from TestU01. Testing in PractRand and SmokeRand is a little bit challenging (it is a 31-bit generator), but if I use the uint31 filter from SmokeRand (adds the high-quality pseudorandom lowest bit from other PRNG) - it passes PractRand at least up to 2 TiB.

References: