spectral test

Knuth defines a figure of merit, which describes how close the separation $1/\backslash 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

}} Associated software and data at https://github.com/vigna/CPRNG.{{rp|3}}

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

where $a,\; m,\; \backslash nu\_d$ are defined as before, and $\backslash gamma\_d$ is the Hermite constant of dimension d. $\backslash gamma^\{1/2\}\_d\; \backslash sqrt[d]\{m\}$ is the smallest possible interplane separation.{{rp|3}}

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 [https://www.iro.umontreal.ca/~lecuyer/myftp/papers/latrules99Errata.pdf Errata] as well.

Again under re-notation, $\backslash mathcal\{M\}^+\_d(m,\; a)$ is the minimum $f\_d$ for a LCG from dimensions 2 to $d$, and $\backslash 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.{{rp|13}} They further define a "harmonic" weighted average figure of merit, $\backslash mathcal\{H\}^+\_d(m,\; a)$ (and $\backslash mathcal\{H\}^*\_d(m,\; a)$).{{rp|13}}

A small variant of the infamous RANDU, with $x\_\{n+1\}\; =\; 65539\; \backslash ,\; x\_n\; \backslash bmod\; 2^\{29\}$ has:{{rp|at=(Table 1)}}

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

George Marsaglia (1972) considers $x\_\{n+1\}\; =\; 69069\; \backslash ,\; x\_n\; \backslash 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.{{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}}

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

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.{{rp|14–5}} For example, they report that the best 17-bit a for m = 2³² is:

• For an LCG (c ≠ 0), {{tt|0x1dab5}} (121525). $\backslash mathcal\{M\}^\{+\}\_8=0.6403$, $\backslash mathcal\{H\}^\{+\}\_8\; =\; 0.6588$.{{rp|14}}
• For an MCG (c = 0), {{tt|0x1e92d}} (125229). $\backslash mathcal\{M\}^\{*\}\_8=0.6623$, $\backslash mathcal\{H\}^\{*\}\_8\; =\; 0.7497$.{{rp|14}}

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

}}

{{notelist}}

{{reflist}}

• {{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}} – lists the $f\_d$ (notated as $S\_s$ 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