{{Short description|Statistical test for linear congruential generators}} [[Image:Randu.png|thumb|right|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).<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 }} 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