My notes on testing PRNGs

[peteroupc]

I have written a page on testing PRNGs for high-quality randomness, more specifically, testing whether the PRNG produces a sequence of numbers that behave like independent uniform random numbers. If a PRNG does well in statistical testing (and meets my other criteria of a high-quality PRNG), only then should we discuss its other aspects (such as performance and ease of implementation).

The following are some points on PRNG testing:

• There are many kinds of PRNGs, including traditional, counter-based, and splittable PRNGs, as well as PRNGs that combine two or more other PRNGs, and there are different approaches to testing all these kinds.

• Many PRNGs have a cycle length so large that no (empirical) statistical test can evaluate all the numbers in the cycle in a reasonable time. At most, the test can only look at a small fraction of the PRNG's behavior (e.g., PractRand has a limit of 32 TiB, or 2^46 bytes). The most demanding simulations may require still fewer random numbers, e.g., 10^11 numbers at most. I currently consider a PRNG statistically good if it doesn't fail PractRand at 1 TiB (2^40 bytes) (where I don't consider "unusual" or "suspicious" results, as opposed to "FAILs", to be failures). Is this threshold too low or too high?

• Different PRNGs have different ways to produce independent random number sequences ("streams"), such as by incrementing a seed, or discarding a huge number of outputs. A given stream strategy can be tested by interleaving the outputs of those streams. I am currently testing two or four PRNGs with consecutive seeds, as well as two or four PRNGs that are "jumped ahead" in the manner supported by the PRNG. It may also be useful to test streams interleaved byte-by-byte, rather than output-by-output, which I haven't noted yet; an example is in the "ShiShuA" PRNG at https://github.com/espadrine/shishua.

• A relatively low-quality PRNG can be combined with another number sequence to produce a high-quality PRNG, enough to show no PractRand failure at 1 TiB (see "Combined PRNGs" for details). A notable example is L'Ecuyer's combined multiple recursive generators.

• Counter-based PRNGs and splittable PRNGs (such as the PRNG used in JAX) can be based on hash functions and other mixing functions, so it's useful to test these functions to see if they are viable for use in these kinds of PRNGs. (I give some of these constructions in detail.) On the subject of mixing functions, a testing procedure by P. Evensen may be of interest.