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 u 1 , u 2 , … {\displaystyle u_{1},u_{2},\dots } . Let 1 / ν t {\displaystyle 1/\nu _{t}} be the maximal separation between covering parallel planes of the sequence { ( u n + 1 : n + t ) ∣ n = 0 , 1 , … } {\displaystyle \{(u_{n+1:n+t})\mid n=0,1,\dots \}} . The spectral test checks that the sequence ν 2 , ν 3 , ν 4 , … {\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. μ 2 = π ν 2 2 / m , μ 3 = 4 3 π ν 3 3 / m , μ 4 = 1 2 π 2 ν 4 4 / m , μ 5 = 8 15 π 2 ν 5 5 / m , μ 6 = 1 6 π 3 ν 6 6 / m , {\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 m {\displaystyle m} is the modulus of the LCG.

Knuth defines a figure of merit, which describes how close the separation 1 / ν t {\displaystyle 1/\nu _{t}} is to the theoretical minimum. Under Steele & Vigna's re-notation, for a dimension d {\displaystyle d} , the figure f d {\displaystyle f_{d}} is defined as^[7]: 3 f d ( m , a ) = ν d / ( γ d 1 / 2 m d ) , {\displaystyle f_{d}(m,a)=\nu _{d}/\left(\gamma _{d}^{1/2}{\sqrt[{d}]{m}}\right),} where a , m , ν d {\displaystyle a,m,\nu _{d}} are defined as before, and γ d {\displaystyle \gamma _{d}} is the Hermite constant of dimension d. γ d 1 / 2 m 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 f d {\displaystyle f_{d}} across a number of dimensions.^[8] Again under re-notation, M d + ( m , a ) {\displaystyle {\mathcal {M}}_{d}^{+}(m,a)} is the minimum f d {\displaystyle f_{d}} for a LCG from dimensions 2 to d {\displaystyle d} , and M d ∗ ( m , a ) {\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 c = 0 {\displaystyle c=0} . Steele & Vigna note that the f d {\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, H d + ( m , a ) {\displaystyle {\mathcal {H}}_{d}^{+}(m,a)} (and H d ∗ ( m , a ) {\displaystyle {\mathcal {H}}_{d}^{*}(m,a)} ).^[7]: 13

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

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

George Marsaglia (1972) considers x n + 1 = 69069 x n mod 2 32 {\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]

The aggregate figures of merit are: M 8 ∗ ( 69069 , 2 32 ) = 0.313127 {\displaystyle {\mathcal {M}}_{8}^{*}(69069,2^{32})=0.313127} , H 8 ∗ ( 69069 , 2 32 ) = 0.449578 {\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 f d {\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). M 8 + = 0.6403 {\displaystyle {\mathcal {M}}_{8}^{+}=0.6403} , H 8 + = 0.6588 {\displaystyle {\mathcal {H}}_{8}^{+}=0.6588} .^[7]: 14
• For an MCG (c = 0), 0x1e92d (125229). M 8 ∗ = 0.6623 {\displaystyle {\mathcal {M}}_{8}^{*}=0.6623} , H 8 ∗ = 0.7497 {\displaystyle {\mathcal {H}}_{8}^{*}=0.7497} .^[7]: 14

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.

• Entacher, Karl (January 1998). "Bad subsequences of well-known linear congruential pseudorandom number generators". ACM Transactions on Modeling and Computer Simulation. 8 (1): 61–70. doi:10.1145/272991.273009. – lists the f d {\displaystyle f_{d}} (notated as S s {\displaystyle S_{s}} in this text) of many well-known LCGs
  • An expanded version of this work is available as: Entacher, Karl (2001). "A Collection of Selected Pseudorandom Number Generators With Linear Structures - extended version".