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.

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.

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 ${\displaystyle u_{1},u_{2},\dots }$. Let ${\displaystyle 1/\nu _{t}}$ be the maximal separation between covering parallel planes of the sequence ${\displaystyle \{(u_{n+1:n+t})\mid n=0,1,\dots \}}$. The spectral test checks that the sequence ${\displaystyle \nu _{2},\nu _{3},\nu _{4},\dots }$ does not decay too quickly.

Knuth recommends checking that each of the following 5 numbers is larger than 0.01. $${\displaystyle {\begin{aligned}\mu _{2}&=\pi \nu _{2}^{2}/m,&\mu _{3}&={\frac {4}{3}}\pi \nu _{3}^{3}/m,&\mu _{4}&={\frac {1}{2}}\pi ^{2}\nu _{4}^{4}/m,\\[1ex]&&\mu _{5}&={\frac {8}{15}}\pi ^{2}\nu _{5}^{5}/m,&\mu _{6}&={\frac {1}{6}}\pi ^{3}\nu _{6}^{6}/m,\end{aligned}}}$$ where ${\displaystyle m}$ is the modulus of the LCG.

Figures of merit

Knuth defines a figure of merit, which describes how close the separation ${\displaystyle 1/\nu _{t}}$ is to the theoretical minimum. Under Steele & Vigna's re-notation, for a dimension ${\displaystyle d}$, the figure ${\displaystyle f_{d}}$ is defined as^[7]: 3 $${\displaystyle f_{d}(m,a)=\nu _{d}/\left(\gamma _{d}^{1/2}{\sqrt[{d}]{m}}\right),}$$ where ${\displaystyle a,m,\nu _{d}}$ are defined as before, and ${\displaystyle \gamma _{d}}$ is the Hermite constant of dimension d. ${\displaystyle \gamma _{d}^{1/2}{\sqrt[{d}]{m}}}$ is the smallest possible interplane separation.^[7]: 3

L'Ecuyer 1991 further introduces two measures corresponding to the minimum of ${\displaystyle f_{d}}$ across a number of dimensions.^[8] Again under re-notation, ${\displaystyle {\mathcal {M}}_{d}^{+}(m,a)}$ is the minimum ${\displaystyle f_{d}}$ for a LCG from dimensions 2 to ${\displaystyle d}$, and ${\displaystyle {\mathcal {M}}_{d}^{*}(m,a)}$ is the same for a multiplicative congruential pseudorandom number generator (MCG), i.e. one where only multiplication is used, or ${\displaystyle c=0}$. Steele & Vigna note that the ${\displaystyle f_{d}}$ is calculated differently in these two cases, necessitating separate values.^[7]: 13 They further define a "harmonic" weighted average figure of merit, ${\displaystyle {\mathcal {H}}_{d}^{+}(m,a)}$ (and ${\displaystyle {\mathcal {H}}_{d}^{*}(m,a)}$).^[7]: 13

Examples

A small variant of the infamous RANDU, with ${\displaystyle x_{n+1}=65539\,x_{n}{\bmod {2}}^{29}}$ has:^{[4]: (Table 1)}

d	2	3	4	5	6	7	8
ν2 d	536936458	118	116	116	116
μd	3.14	10−5	10−4	10−3	0.02
fd[a]	0.520224	0.018902	0.084143	0.207185	0.368841	0.552205	0.578329

The aggregate figures of merit are: ${\displaystyle {\mathcal {M}}_{8}^{*}(65539,2^{29})=0.018902}$, ${\displaystyle {\mathcal {H}}_{8}^{*}(65539,2^{29})=0.330886}$.^[a]

George Marsaglia (1972) considers ${\displaystyle x_{n+1}=69069\,x_{n}{\bmod {2}}^{32}}$ as "a candidate for the best of all multipliers" because it is easy to remember, and has particularly large spectral test numbers.^[9]

d	2	3	4	5	6	7	8
ν2 d	4243209856	2072544	52804	6990	242
μd[b]	3.10	2.91	3.20	5.01	0.017
fd[a]	0.462490	0.313127	0.457183	0.552916	0.376706	0.496687	0.685247

The aggregate figures of merit are: ${\displaystyle {\mathcal {M}}_{8}^{*}(69069,2^{32})=0.313127}$, ${\displaystyle {\mathcal {H}}_{8}^{*}(69069,2^{32})=0.449578}$.^[a]

Steele & Vigna (2020) provide the multipliers with the highest aggregate figures of merit for many choices of m = 2ⁿ and a given bit-length of a. They also provide the individual ${\displaystyle f_{d}}$ values and a software package for calculating these values.^{[7]: 14–5} For example, they report that the best 17-bit a for m = 2³² is:

• For an LCG (c ≠ 0), 0x1dab5 (121525). ${\displaystyle {\mathcal {M}}_{8}^{+}=0.6403}$, ${\displaystyle {\mathcal {H}}_{8}^{+}=0.6588}$.^[7]: 14
• For an MCG (c = 0), 0x1e92d (125229). ${\displaystyle {\mathcal {M}}_{8}^{*}=0.6623}$, ${\displaystyle {\mathcal {H}}_{8}^{*}=0.7497}$.^[7]: 14

Additional illustration

Despite the fact that both relations pass the Chi-squared test, the first LCG is less random than the second, as the range of values it can produce by the order it produces them in is less evenly distributed.