Spectral test

---

title: "Spectral test" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["pseudorandom-number-generators"] description: "Statistical test for linear congruential generators" topic_path: "general/pseudorandom-number-generators" source: "https://en.wikipedia.org/wiki/Spectral_test" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Statistical test for linear congruential generators ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/3/38/Randu.png" caption="plane]]s."] ::

The spectral test is a statistical test for the quality of a class of pseudorandom number generators (PRNGs), the linear congruential generators (LCGs). 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.{{cite journal |title=Random Numbers Fall Mainly in the Planes |first=George |last=Marsaglia |authorlink=George Marsaglia |journal=PNAS |date=September 1968 |volume=61 |issue=1 |pages=25–28 |doi=10.1073/pnas.61.1.25 |doi-access=free |bibcode=1968PNAS...61...25M |pmc=285899 |url=https://www.pnas.org/content/61/1/25.full.pdf |pmid=16591687

According to Donald Knuth, this is by far the most powerful test known, because it can fail LCGs which pass most statistical tests. The IBM subroutine RANDU{{cite journal |title=IBM/360 Scientific Subroutine Package (360A-CM-03X) Version III |id=Scientific Application Program H20-0205-3 |publisher=IBM Technical Publications Department |location=White Plains, NY |year=1968 |volume=II |doi=10.3247/SL2Soft08.001 |page=77 |url=http://www.ebyte.it/library/downloads/IBM_System360_SSP.pdf#page=81 |author=((International Business Machines Corporation)) |journal=Stan's Library

Let the PRNG generate a sequence u_1, u_2, \dots. Let 1/\nu_t be the maximal separation between covering parallel planes of the sequence {(u_{n+1:n+t}) \mid n = 0, 1, \dots}. The spectral test checks that the sequence \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. \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 is the modulus of the LCG.

Figures of merit

Knuth defines a figure of merit, which describes how close the separation 1/\nu_t is to the theoretical minimum. Under Steele & Vigna's re-notation, for a dimension d, the figure f_d is defined as{{cite journal |title=Computationally easy, spectrally good multipliers for congruential pseudorandom number generators |first1=Guy L. Jr. |last1=Steele |author-link1=Guy L. Steele Jr. |first2=Sebastiano |last2=Vigna |author-link2=Sebastiano Vigna |journal=Software: Practice and Experience |volume=52 |issue=2 |date=February 2022 |pages=443–458 |doi=10.1002/spe.3030 |doi-access=free |arxiv=2001.05304 |orig-date=15 January 2020 |url=https://www.researchgate.net/publication/354960552 f_d(m, a) = \nu_d / \left(\gamma^{1/2}_d \sqrt[d]{m}\right), where a, m, \nu_d are defined as before, and \gamma_d is the Hermite constant of dimension d. \gamma^{1/2}_d \sqrt[d]{m} is the smallest possible interplane separation.

L'Ecuyer 1991 further introduces two measures corresponding to the minimum of f_d across a number of dimensions.{{cite journal |first=Pierre |last=L'Ecuyer |title=Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure |journal=Mathematics of Computation |volume=68 |issue=225 |pages=249–260 |date=January 1999 |url=https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf |doi=10.1090/S0025-5718-99-00996-5 |bibcode=1999MaCom..68..249L |citeseerx=10.1.1.34.1024}} Be sure to read the Errata as well. Again under re-notation, \mathcal{M}^+_d(m, a) is the minimum f_d for a LCG from dimensions 2 to d, and \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. Steele & Vigna note that the f_d is calculated differently in these two cases, necessitating separate values. They further define a "harmonic" weighted average figure of merit, \mathcal{H}^+_d(m, a) (and \mathcal{H}^_d(m, a)).

Examples

A small variant of the infamous RANDU, with x_{n+1} = 65539 , x_n \bmod 2^{29} has:

::data[format=table]

d	ν	*μ*d	f**d
2	3	4	5
536936458	118	116	116
3.14	10−5	10−4	10−3
0.520224	0.018902	0.084143	0.207185
::

The aggregate figures of merit are: \mathcal{M}^{}_8(65539, 2^{29}) = 0.018902, \mathcal{H}^{}_8(65539, 2^{29}) = 0.330886.

George Marsaglia (1972) considers 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.

::data[format=table]

d	ν	*μ*d	f**d
2	3	4	5
4243209856	2072544	52804	6990
3.10	2.91	3.20	5.01
0.462490	0.313127	0.457183	0.552916
::

The aggregate figures of merit are: \mathcal{M}^{}_8(69069, 2^{32}) =0.313127, \mathcal{H}^{}_8(69069, 2^{32}) = 0.449578.

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 f_d values and a software package for calculating these values. For example, they report that the best 17-bit a for m = 232 is:

• For an LCG (c ≠ 0), (121525). \mathcal{M}^{+}_8=0.6403, \mathcal{H}^{+}_8 = 0.6588.
• For an MCG (c = 0), (125229). \mathcal{M}^{}_8=0.6623, \mathcal{H}^{}_8 = 0.7497.

Additional illustration

|width=300 |align=center |direction=horizontal |image1=Spectral test of 3x mod 31.png |image2=Spectral test of 13x mod 31.png |footer=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

References

1. (1 Aug 1996). "Testing Random Number Generators, Part 2". [[Dr. Dobb's Journal]].
2. "Testing Random-Number Generators (Lecture)".
3. (1981). "[[The Art of Computer Programming]] volume 2: Seminumerical algorithms". [[Addison-Wesley]].
4. IBM, ''System/360 Scientific Subroutine Package,'' Version II, Programmer's Manual, H20-0205-1, 1967, p. 54.
5. Marsaglia, GEORGE. (1972-01-01). "The Structure of Linear Congruential Sequences". Academic Press.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::