Spectral test explained

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,...

. Let

1/\nu_t

be the maximal separation between covering parallel planes of the sequence

\{(u_n+1:n+t)\midn=0,1,...\}

. The spectral test checks that the sequence

\nu_2,\nu_3,\nu_4,...

does not decay too quickly.

Knuth recommends checking that each of the following 5 numbers is larger than 0.01. $\begin \mu_2 &= \pi \nu_2^2 / m, & \mu_3 &= \frac \pi \nu_3^3 / m, & \mu_4 &= \frac \pi^2 \nu_4^4 / m, \\[1ex] & & \mu_5 &= \frac \pi^2 \nu_5^5 / m, & \mu_6 &= \frac \pi^3 \nu_6^6 / m,\end$ where

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

, the figure

f_d

is defined as^[7]

f_d(m, a) = \nu_d / \left(\gamma^_d \sqrt[d]\right),

where

a,m,\nu_d

are defined as before, and

\gamma_d

is the Hermite constant of dimension d.

	1/2
\gamma
	d

\sqrt[d]{m}

is the smallest possible interplane separation.^[7]

L'Ecuyer 1991 further introduces two measures corresponding to the minimum of

f_d

across a number of dimensions.^[8] Again under re-notation,

	+
l{M}
	d(m,

is the minimum

f_d

for a LCG from dimensions 2 to

, and

	*
l{M}
	d(m,

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.^[7] They further define a "harmonic" weighted average figure of merit,

	+
l{H}
	d(m,

(and

	*
l{H}
	d(m,

).^[7]

Examples

A small variant of the infamous RANDU, with

x_n+1=65539x_n\bmod2²⁹

has:

d	2	3	4	5	6	7	8
ν	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:

	*
l{M}
	8(65539,

2²⁹)=0.018902

	*
l{H}
	8(65539,

2²⁹)=0.330886

George Marsaglia (1972) considers

x_n+1=69069x_n\bmod2³²

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
ν	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:

	*
l{M}
	8(69069,

2³²)=0.313127

	*
l{H}
	8(69069,

2³²)=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.^[7] For example, they report that the best 17-bit a for m = 2³² is:

For an LCG (c ≠ 0), (121525).

	+
l{M}
	8=0.6403

	+
l{H}
	8

=0.6588

.^[7]

For an MCG (c = 0), (125229).

	*
l{M}
	8=0.6623

	*
l{H}
	8

=0.7497

.^[7]

Notes and References

.
Random Numbers Fall Mainly in the Planes . George . Marsaglia . George Marsaglia . . September 1968 . 61 . 1 . 25–28 . 10.1073/pnas.61.1.25 . free . 1968PNAS...61...25M . 285899 . 16591687 .
Web site: Jain. Raj. Testing Random-Number Generators (Lecture). Washington University in St. Louis. 2 December 2016.
.
IBM, System/360 Scientific Subroutine Package, Version II, Programmer's Manual, H20-0205-1, 1967, p. 54.
IBM/360 Scientific Subroutine Package (360A-CM-03X) Version III . Scientific Application Program H20-0205-3 . IBM Technical Publications Department . White Plains, NY . 1968 . II . 10.3247/SL2Soft08.001 . 77 . ((International Business Machines Corporation)) . Stan's Library .
Computationally easy, spectrally good multipliers for congruential pseudorandom number generators . Guy L. Jr. . Steele . Guy L. Steele Jr. . Sebastiano . Vigna . Sebastiano Vigna . Software: Practice and Experience . 52 . 2 . February 2022 . 443–458 . 10.1002/spe.3030 . free . 2001.05304 . 15 January 2020 . Associated software and data at https://github.com/vigna/CPRNG.
Pierre . L'Ecuyer . Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure . . 68 . 225 . 249–260 . January 1999 . 10.1090/S0025-5718-99-00996-5 . 1999MaCom..68..249L . 10.1.1.34.1024. Be sure to read the Errata as well.

Spectral test explained

Figures of merit

Examples

Further reading

Notes and References