Encyclopedia

Spectral test

Statistical test for linear congruential generators

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated June 23, 2026

Image credit is listed at the end of this article.

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. The spectral test compares the distance between these planes; the further apart they are, the worse the generator is. 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, this is by far the most powerful test known, because it can fail LCGs which pass most statistical tests. The IBM subroutine RANDU LCG fails in this test for 3 dimensions and above.

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.

01Figures 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 $f_{d}(m,a)=\nu _{d}/\left(\gamma _{d}^{1/2}{\sqrt[{d}]{m}}\right),$ where $a,m,\nu _{d}$ are defined as before, and $\gamma _{d}$ is the Hermite constant of dimension d. $\gamma _{d}^{1/2}{\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. 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)$ ).

02Examples

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

d	2	3	4	5	6	7	8
ν² _d	536936458	118	116	116	116
μ_d	3.14	10⁻⁵	10⁻⁴	10⁻³	0.02
f_d	0.520224	0.018902	0.084143	0.207185	0.368841	0.552205	0.578329

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.

d	2	3	4	5	6	7	8
ν² _d	4243209856	2072544	52804	6990	242
μ_d	3.10	2.91	3.20	5.01	0.017
f_d	0.462490	0.313127	0.457183	0.552916	0.376706	0.496687	0.685247

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 = 2ⁿ 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 = 2³² is:

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

Watch videos about Spectral testExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Spectral test”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Randu.png by The original uploader was Luis Sanchez at English Wikipedia., CC BY-SA 3.0

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.