Spectral test

The spectral test is a statistical test for the quality of a class of pseudorandom number generators (PRNGs), the linear congruential generators (LCGs).

[1] LCGs have a property that when plotted in 2 or more dimensions, lines or hyperplanes will form, on which all possible outputs can be found.

[2] The spectral test compares the distance between these planes; the further apart they are, the worse the generator is.

[3] As this test is devised to study the lattice structures of LCGs, it can not be applied to other families of PRNGs.

According to Donald Knuth,[4] this is by far the most powerful test known, because it can fail LCGs which pass most statistical tests.

The IBM subroutine RANDU[5][6] LCG fails in this test for 3 dimensions and above.

Let the PRNG generate a sequence

be the maximal separation between covering parallel planes of the sequence

The spectral test checks that the sequence

Knuth recommends checking that each of the following 5 numbers is larger than 0.01.

is the modulus of the LCG.

Knuth defines a figure of merit, which describes how close the separation

Under Steele & Vigna's re-notation, for a dimension

is the Hermite constant of dimension d.

is the smallest possible interplane separation.

[7]: 3 L'Ecuyer 1991 further introduces two measures corresponding to the minimum of

across a number of dimensions.

for a LCG from dimensions 2 to

is the same for a multiplicative congruential pseudorandom number generator (MCG), i.e. one where only multiplication is used, or

Steele & Vigna note that the

is calculated differently in these two cases, necessitating separate values.

[7]: 13  They further define a "harmonic" weighted average figure of merit,

[7]: 13 A small variant of the infamous RANDU, with

has:[4]: (Table 1) The aggregate figures of merit are:

[a] George Marsaglia (1972) considers

as "a candidate for the best of all multipliers" because it is easy to remember, and has particularly large spectral test numbers.

[9] The aggregate figures of merit are:

[a] Steele & Vigna (2020) provide the multipliers with the highest aggregate figures of merit for many choices of m = 2n and a given bit-length of a.

They also provide the individual

values and a software package for calculating these values.

Three-dimensional plot of 100,000 values generated with RANDU . Each point represents 3 consecutive pseudorandom values. It is clearly seen that the points fall in 15 two-dimensional planes .