Does It Beat the Minimal Standard?

Suppose that you've written (or just seen someone else announce) a brand new PRNG. Cool! It's nice to have new things. But here's the question you should ask yourself; “Is it better than a reasonable ‘minimal standard’? Does it beat methods devised more than sixty years ago?”

Wisdom from the Past

Back in 1987, more than thirty years ago now, Steve Park and Keith Miller wrote the paper Random Number Generators: Good Ones Are Hard to Find, which lamented the poor quality of many of the PRNGs in use at the time and proposed a bare mininum for a “good enough” PRNG (the paper appeared in CACM early the following year). In that paper, they wrote

In retrospect it is evident that a generally satisfactory algorithm for random number generation was proposed by D. H. Lehmer 36 years ago [26]. This parametric multiplicative linear congruential algorithm has withstood the test of time. It can be implemented efficiently [27, 31, 37, 41], numerous empirical tests of the randomness of its output have been published [8, 15, 27, 28, 37], and its important theoretical properties have been analyzed [9, 14, 18, 30]. The conclusion to be drawn from all this research is now clear. Although Lehmer’s algorithm has some statistical defects, if the algorithm parameters are chosen properly and if the software implementation of the algorithm is correct, the resulting generator can produce a virtually infinite sequence of numbers that will satisfy almost any statistical test of randomness. In other words, with properly chosen parameters, Lehmer’s algorithm, correctly implemented, represents a good minimal standard generator against which all other random number generators can—and should—be judged.

Thirty years later, some specifics may have changed (i.e., the necessary parameters for what we might consider a reasonable LCG), but the fundamental idea—that any proponent of a new PRNG should be asked to explain how their technique is better than an appropriate “minimal standard” LCG—remains as relevant today is it was then.

If you can't show that your PRNG technique beats an idea from over sixty years ago, you haven't proven its worth.

Today's 32-bit Minimal Standard: A 96-bit Truncated LCG or MCG

The code below represents a reasonable minimal-standard MCG:

uint96_t state = 1;   // can be seeded to any odd number

uint32_t next()
{
    state *= 0xdc87976860b11728995deb95;
    return state >> 64;
}

And this version is a reasonable minimal-standard LCG:

uint96_t state;   // can be seeded to any number

uint32_t next()
{
    const uint96_t MULTIPLIER = 0xc580cadd754f7336d2eaa27d;
    state *= MULTIPLIER;
    state += MULTIPLIER;
        // Any odd odd number will do, the multiplier is odd and
        // conveniently to hand
    return state >> 64;
}

What we know about these two PRNGs is that

• The code is incredibly simple (although it does presume the existence of a 96-bit (or larger) integer type).
• On 64-bit machines, the necessary multiplication is not difficult to perform. In fact, on modern x86 machines, the entire generation process can take place in less than a nanosecond.
• The generators are known to have long periods and no short cycles. The LCG has period 2⁹⁶, which is maximal, and no bad initializations—any initial seed is okay. The MCG provides two separate cycles of size 2⁶² and only requires that the seed be odd.
• The underlying theory ensures that the generators are uniform (each output occurs the same number of times).
• Because the output function is truncation, each output occurs a vast number of times (2⁶² and 2⁶⁴, respectively), meaning that producing one output does not significantly reduce the chance of it recurring.
• The underlying theory is very well understood. The multiplicative constants were chosen to have excellent “spectral test” values (for the MCG, normalized LLL-spectral test values are M₈ = 0.70279, M₁₆ = 0.65345, M₂₄ = 0.58118 and for the LCG, M₈ = 0.73201, M₁₆ = 0.64438, M₂₄ = 0.53151, as computed by software by Karl Entacher).
• The output passes stringent statistical tests, such as PractRand up to 32 TB and TestU01's BigCrush test.

In fact, not only does this 96-bit PRNG pass statistical tests, it passes them well. Testing with PractRand, we can plot the failure point for different sized 32-bit generators as follows:

This graph shows us that we leave clear-fail territory at 78 bits for LCGs and 80 bits for MCGs. Thus a 96-bit LCG or MCG has considerable headroom available to allow it to pass larger statistical tests.

Extrapolating the line from this graph shows that we'll get to the clear failure point for a 96-bit MCG at 128 petabytes of data, and for the LCG at the half exabyte point. If it takes PractRand a week of testing to test 32 TB, half an exabyte will require more than three hundred years of testing to detect statistical flaws.

Today's 64-bit Minimal Standard: A 128-bit Truncated LCG or MCG

Similarly, if you want 64-bit output, a 128-bit truncated LCG or MCG represents a reasonable minimal standard. In fact, on 64-bit hardware, these generators are no more costly to compute that the 32-bit output versions given above.

uint128_t state = 1;   // can be seeded to any odd number

uint64_t next()
{
    state *= 0x0fc94e3bf4e9ab32866458cd56f5e605;
            // Spectral test: M8 = 0.71005, M16 = 0.66094, M24 = 0.61455
    return state >> 64;
}

uint128_t state;   // can be seeded to any number

uint64_t next()
{
    const uint128_t MULTIPLIER = 0x2d99787926d46932a4c1f32680f70c55;
    state *= MULTIPLIER;
        // Spectral test: M8 = 0.70420, M16 = 0.65412, M24 = 0.60209
    state += MULTIPLIER;
        // Any odd odd number will do, the multiplier is odd and
        // conveniently to hand
    return state >> 64;
}

Essentially the same observations we made for the 32-bit generators apply here as well. Once again, we can plot the failure point for different sized 64-bit generators as follows:

This graph shows us that we leave clear-fail territory at 109 bits for LCGs and 111 bits for MCGs. Thus a 128-bit LCG or MCG has considerable headroom available to allow it to pass larger statistical tests.

As before, we can extrapolate the line from this graph, this time finding that we reach the clear failure point for a 128-bit MCG at 256 petabytes of data, and for the LCG at the 1 exabyte point. If it takes PractRand a week of testing to test 32 TB, an exabyte will require more than six hundred years of testing to detect statistical flaws.

Conclusion

Linear congruential generators are frequently cited as being a poor choice for random-number generation, and at small sizes that remains true, but as we have seen, at larger sizes these generators do very well in statistical tests. Forty years ago, these larger versions might have been unwieldy, but that has not been the case for a long time. Today modern 64-bit architectures have little difficulty performing 128-bit math quickly, and since 2016, even a $35 Raspberry Pi has a 64-bit quad-core CPU. And older 32-bit machines can perform 96-bit math acceptably fast—it's worth realizing that the longstanding drand48 generator present in all Unix systems was designed in the age of 16-bit machines and can be trivially adapted to use 32-bit data, creating drand96.

Any new PRNG with 64-bit output needs to answer the question, “How is it better than the minimal standard, a 128-bit LCG?” and likewise any PRNG with 32-bit output needs to answer the question “How is it better than the minimal standard, a 96-bit LCG?”. It is not enough just to be fairly fast, because these minimal standards are fast. It is not enough to pass stringent statistical tests, because these minimal standard generators pass those same tests, and pass them easily.

Moreover, the graphs we have seen show that it is possible to take a scientific approach to testing PRNGs. The trend lines we have seen allow us to make good predictions about tests that that might be prohibitively expensive to run, so we see another useful tip for designers of PRNGs. Don't just provide a single data point, provide many and do some science.

Appendix

To allow others to recreate the above graphs, below are multiplicative constants for MCGs and LCGs of different sizes. The constants were found by using a random search to find constants that had good normalized LLL-spectral test results; each constant is intended to be “very good” rather than truly outstanding. Each table shows the M₈ result for the normalized LLL-spectral test. The M₁₆ values are all above 0.625.

MCG Constants

LCG Constants