Spectral test
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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). 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.…
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). 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. f_d(m, a) = \nu_d / \left(\gamma^{1/2}_d \sqrt[d]{m}\right), where a, m, \nu_d are defined as before, and \gamma_d is the Hermite constant of dimension d. \gamma^{1/2}_d \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) ). A small variant of the infamous RANDU, with x_{n+1} = 65539 \, x_n \bmod 2^{29} has: 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. 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 n 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 32 is: For an LCG (c ≠ 0), (121525). \mathcal{M}^{+}_8=0.6403 , \mathcal{H}^{+}_8 = 0.6588 . For an MCG (c = 0), (125229). \mathcal{M}^{*}_8=0.6623 , \mathcal{H}^{*}_8 = 0.7497 .
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1360738404 under CC BY-SA 4.0; modifications have been made.