Spectral test

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.

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 ${\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})|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}/(\gamma _{d}^{\tfrac {1}{2}}{\sqrt[{d}]{m}})}$,

where ${\displaystyle a,m,\nu _{d}}$ are defined as before, and ${\displaystyle \gamma _{d}}$ being the Hermite constant of dimension d. ${\displaystyle \gamma _{d}^{\tfrac {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 [lower-alpha 1]	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}$. ^{[lower-alpha 1]}

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 [lower-alpha 2]	3.10	2.91	3.20	5.01	0.017
fd [lower-alpha 1]	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}$. ^{[lower-alpha 1]}

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.

References

1. Calculated using software from Steele & Vigna (2020), program "mspect" (src/spect.cpp, multiplicative mode).
2. Calculated from ν²
   _d reported by Marsaglia.

1. Williams, K. B.; Dwyer, Jerry (1 Aug 1996), "Testing Random Number Generators, Part 2", Dr. Dobb's Journal , retrieved 26 Jan 2012.
2. Marsaglia, George (September 1968). "Random Numbers Fall Mainly in the Planes" (PDF). PNAS . 61 (1): 25–28. Bibcode:1968PNAS...61...25M. doi: 10.1073/pnas.61.1.25 . PMC   285899 . PMID   16591687.
3. Jain, Raj. "Testing Random-Number Generators (Lecture)" (PDF). Washington University in St. Louis . Retrieved 2 December 2016.
4. Knuth, Donald E. (1981), "3.3.4: The Spectral Test", The Art of Computer Programming volume 2: Seminumerical algorithms (2nd ed.), Addison-Wesley .
5. IBM, System/360 Scientific Subroutine Package, Version II, Programmer's Manual, H20-0205-1, 1967, p. 54.
6. International Business Machines Corporation (1968). "IBM/360 Scientific Subroutine Package (360A-CM-03X) Version III" (PDF). Stan's Library. White Plains, NY: IBM Technical Publications Department. II: 77. doi:10.3247/SL2Soft08.001. Scientific Application Program H20-0205-3.
7. Steele, Guy L. Jr.; Vigna, Sebastiano (February 2022) [15 January 2020]. "Computationally easy, spectrally good multipliers for congruential pseudorandom number generators" (PDF). Software: Practice and Experience. 52 (2): 443–458. arXiv: 2001.05304 . doi: 10.1002/spe.3030 . Associated software and data at https://github.com/vigna/CPRNG.
8. L'Ecuyer, Pierre (January 1999). "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure" (PDF). Mathematics of Computation . 68 (225): 249–260. Bibcode:1999MaCom..68..249L. CiteSeerX   10.1.1.34.1024 . doi:10.1090/S0025-5718-99-00996-5. Be sure to read the Errata as well.
9. Marsaglia, GEORGE (1972-01-01), Zaremba, S. K. (ed.), "The Structure of Linear Congruential Sequences", Applications of Number Theory to Numerical Analysis, Academic Press, pp. 249–285, ISBN   978-0-12-775950-0 , retrieved 2024-01-29

Further reading

• 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 ${\displaystyle f_{d}}$ (notated as ${\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".