View source for Spectral test

[[Image:Randu.png|thumb|right|[[Three-dimensional space|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 [[2D geometric model|two-dimensional]] [[Plane (mathematics)|plane]]s.]]
The '''spectral test''' is a statistical test for the quality of a class of [[pseudorandom number generator]]s (PRNGs), the [[linear congruential generator]]s (LCGs).<ref>{{Citation | last1=Williams | first1=K. B. | last2=Dwyer | first2=Jerry | title=Testing Random Number Generators, Part 2 | url=http://drdobbs.com/184403208 | accessdate=26 Jan 2012 | date=1 Aug 1996 | journal=[[Dr. Dobb's Journal]]}}.</ref> 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.<ref name=Marsaglia68>{{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
 }}</ref> The spectral test compares the distance between these planes; the further apart they are, the worse the generator is.<ref>{{cite web|last1=Jain|first1=Raj|title=Testing Random-Number Generators (Lecture)|url=http://www.cse.wustl.edu/~jain/cse567-08/ftp/k_27trg.pdf|website=[[Washington University in St. Louis]]|accessdate=2 December 2016}}</ref> 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]],<ref name=":0">{{Citation |last1=Knuth |first1=Donald E. |title=[[The Art of Computer Programming]] volume 2: Seminumerical algorithms |year=1981 |chapter=3.3.4: The Spectral Test |edition=2nd |publisher=[[Addison-Wesley]] |author1-link=Donald Knuth}}.</ref> this is by far the most powerful test known, because it can fail LCGs which pass most statistical tests. The IBM subroutine [[RANDU]]<ref>IBM, ''System/360 Scientific Subroutine Package,'' Version II, Programmer's Manual, H20-0205-1, 1967, p. 54.</ref><ref>{{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
 }}</ref> LCG fails in this test for 3 dimensions and above.

Let the PRNG generate a sequence <math>u_1, u_2, \dots</math>. Let <math>1/\nu_t</math> be the maximal separation between covering parallel planes of the sequence <math>\{(u_{n+1:n+t}) \mid n = 0, 1, \dots\}</math>. The spectral test checks that the sequence <math>\nu_2, \nu_3, \nu_4, \dots</math> does not decay too quickly.

Knuth recommends checking that each of the following 5 numbers is larger than 0.01.
<math display="block">
\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}
</math>
where <math>m</math> is the modulus of the LCG.

== Figures of merit ==
Knuth defines a ''figure of merit'', which describes how close the separation  <math>1/\nu_t</math> is to the theoretical minimum. Under Steele & Vigna's re-notation, for a dimension <math>d</math>, the figure <math>f_d</math> is defined as<ref name=Steele20>{{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_Computationally_easy_spectrally_good_multipliers_for_congruential_pseudorandom_number_generators/fulltext/6155d14ae7bb415a5d438c07/Computationally-easy-spectrally-good-multipliers-for-congruential-pseudorandom-number-generators.pdf
}} Associated software and data at https://github.com/vigna/CPRNG.</ref>{{rp|3}}
<math display="block">
 f_d(m, a) = \nu_d / \left(\gamma^{1/2}_d \sqrt[d]{m}\right),
</math>
where <math>a, m, \nu_d</math> are defined as before, and <math>\gamma_d</math> is the [[Hermite constant]] of dimension ''d''. <math>\gamma^{1/2}_d \sqrt[d]{m}</math> is the smallest possible interplane separation.<ref name=Steele20/>{{rp|3}}

L'Ecuyer 1991 further introduces two measures corresponding to the minimum of <math>f_d</math> across a number of dimensions.<ref name=LEcuyer99>{{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 [https://www.iro.umontreal.ca/~lecuyer/myftp/papers/latrules99Errata.pdf Errata] as well.
</ref> Again under re-notation, <math>\mathcal{M}^+_d(m, a)</math> is the minimum <math>f_d</math> for a LCG from dimensions 2 to <math>d</math>, and <math>\mathcal{M}^*_d(m, a)</math> is the same for a multiplicative congruential pseudorandom number generator (MCG), i.e. one where only multiplication is used, or <math>c = 0</math>. Steele & Vigna note that the <math>f_d</math> is calculated differently in these two cases, necessitating separate values.<ref name=Steele20/>{{rp|13}} They further define a "harmonic" weighted average figure of merit, <math>\mathcal{H}^+_d(m, a)</math> (and <math>\mathcal{H}^*_d(m, a)</math>).<ref name=Steele20/>{{rp|13}}

== Examples ==
A small variant of the infamous [[RANDU]], with <math>x_{n+1} = 65539 \, x_n \bmod 2^{29}</math> has:<ref name=":0" />{{rp|at=(Table 1)}}

{|class=wikitable
|-
! ''d''
|2 || 3 || 4 || 5 || 6 || 7 || 8
|-
! ''&nu;''{{su|p=2|b=''d''}}
| 536936458 || 118 || 116 || 116 || 116 
|-
! ''&mu;''<sub>''d''</sub>
| 3.14 || 10<sup>−5</sup> || 10<sup>−4</sup> || 10<sup>−3</sup> || 0.02
|-
! ''f''<sub>''d''</sub>{{efn|name=SSSoft|Calculated using software from Steele & Vigna (2020), program "mspect" (src/spect.cpp, multiplicative mode).}}
|0.520224||0.018902||0.084143||0.207185||0.368841||0.552205||0.578329
|}

The aggregate figures of merit are: <math>\mathcal{M}^{*}_8(65539, 2^{29}) = 0.018902</math>, <math>\mathcal{H}^{*}_8(65539, 2^{29}) = 0.330886</math>.{{efn|name=SSSoft}}

[[George Marsaglia]] (1972) considers <math>x_{n+1} = 69069 \, x_n \bmod 2^{32}</math> as "a candidate for the best of all multipliers" because it is easy to remember, and has particularly large spectral test numbers.<ref>{{Citation |last=Marsaglia |first=GEORGE |title=The Structure of Linear Congruential Sequences |date=1972-01-01 |work=Applications of Number Theory to Numerical Analysis |pages=249–285 |editor-last=Zaremba |editor-first=S. K. |url=https://www.sciencedirect.com/science/article/pii/B9780127759500500133 |access-date=2024-01-29 |publisher=Academic Press |isbn=978-0-12-775950-0}}</ref>

{|class=wikitable
|-
! ''d''
|2 || 3 || 4 || 5 || 6 || 7 || 8
|-
! ''&nu;''{{su|p=2|b=''d''}}
| 4243209856 || 2072544 || 52804 || 6990 || 242
|-
! ''&mu;''<sub>''d''</sub>{{efn|Calculated from ''&nu;''{{su|p=2|b=''d''}} reported by Marsaglia.}}
| 3.10 || 2.91 || 3.20 || 5.01 || 0.017
|-
! ''f''<sub>''d''</sub>{{efn|name=SSSoft}}
|0.462490||0.313127||0.457183||0.552916||0.376706||0.496687||0.685247
|}

The aggregate figures of merit are: <math>\mathcal{M}^{*}_8(69069, 2^{32}) =0.313127</math>, <math>\mathcal{H}^{*}_8(69069, 2^{32}) = 0.449578</math>.{{efn|name=SSSoft}}

Steele & Vigna (2020) provide the multipliers with the highest aggregate figures of merit for many choices of ''m'' = 2<sup>''n''</sup> and a given bit-length of ''a''. They also provide the individual <math>f_d</math> values and a software package for calculating these values.<ref name=Steele20/>{{rp|14&ndash;5}} For example, they report that the best 17-bit ''a'' for ''m'' = 2<sup>32</sup> is:

* For an LCG (c &ne; 0), {{tt|0x1dab5}} (121525). <math>\mathcal{M}^{+}_8=0.6403</math>, <math>\mathcal{H}^{+}_8 = 0.6588</math>.<ref name=Steele20/>{{rp|14}}
* For an MCG (c = 0), {{tt|0x1e92d}} (125229). <math>\mathcal{M}^{*}_8=0.6623</math>, <math>\mathcal{H}^{*}_8 = 0.7497</math>.<ref name=Steele20/>{{rp|14}}

== Additional illustration ==

{{multiple image
|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==
{{notelist}}
{{reflist}}

== Further reading ==
* {{cite journal |last1=Entacher |first1=Karl |title=Bad subsequences of well-known linear congruential pseudorandom number generators |journal=ACM Transactions on Modeling and Computer Simulation |date=January 1998 |volume=8 |issue=1 |pages=61–70 |doi=10.1145/272991.273009}} &ndash; lists the <math>f_d</math> (notated as <math>S_s</math> in this text) of many well-known LCGs
** An expanded version of this work is available as: {{cite web |last1=Entacher |first1=Karl |title=A Collection of Selected Pseudorandom Number Generators With Linear Structures - extended version |url=https://www.researchgate.net/publication/2683298 |date=2001}}

[[Category:Pseudorandom number generators]]