Spectral test
![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Randu.png/220px-Randu.png)
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 . Let be the maximal separation between covering parallel planes of the sequence . The spectral test checks that the sequence does not decay too quickly.
Knuth recommends checking that each of the following 5 numbers is larger than 0.01. where is the modulus of the LCG.
Figures of merit
[edit]Knuth defines a figure of merit, which describes how close the separation is to the theoretical minimum. Under Steele & Vigna's re-notation, for a dimension , the figure is defined as[7]: 3 where are defined as before, and is the Hermite constant of dimension d. is the smallest possible interplane separation.[7]: 3
L'Ecuyer 1991 further introduces two measures corresponding to the minimum of across a number of dimensions.[8] Again under re-notation, is the minimum for a LCG from dimensions 2 to , and is the same for a multiplicative congruential pseudorandom number generator (MCG), i.e. one where only multiplication is used, or . Steele & Vigna note that the is calculated differently in these two cases, necessitating separate values.[7]: 13 They further define a "harmonic" weighted average figure of merit, (and ).[7]: 13
Examples
[edit]A small variant of the infamous RANDU, with has:[4]: (Table 1)
d | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|
d |
536936458 | 118 | 116 | 116 | 116 | ||
3.14 | 10−5 | 10−4 | 10−3 | 0.02 | |||
fd[a] | 0.520224 | 0.018902 | 0.084143 | 0.207185 | 0.368841 | 0.552205 | 0.578329 |
The aggregate figures of merit are: , .[a]
George Marsaglia (1972) considers as "a candidate for the best of all multipliers" because it is easy to remember, and has particularly large spectral test numbers.[9]
d | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|
d |
4243209856 | 2072544 | 52804 | 6990 | 242 | ||
3.10 | 2.91 | 3.20 | 5.01 | 0.017 | |||
fd[a] | 0.462490 | 0.313127 | 0.457183 | 0.552916 | 0.376706 | 0.496687 | 0.685247 |
The aggregate figures of merit are: , .[a]
Steele & Vigna (2020) provide the multipliers with the highest aggregate figures of merit for many choices of m = 2n and a given bit-length of a. They also provide the individual values and a software package for calculating these values.[7]: 14–5 For example, they report that the best 17-bit a for m = 232 is:
Additional illustration
[edit]References
[edit]- ^ Williams, K. B.; Dwyer, Jerry (1 Aug 1996), "Testing Random Number Generators, Part 2", Dr. Dobb's Journal, retrieved 26 Jan 2012.
- ^ Marsaglia, George (September 1968). "Random Numbers Fall Mainly in the Planes" (PDF). PNAS. 61 (1): 25–28. Bibcode:1968PNAS...61...25M. doi:10.1073/pnas.61.1.25. PMC 285899. PMID 16591687.
- ^ Jain, Raj. "Testing Random-Number Generators (Lecture)" (PDF). Washington University in St. Louis. Retrieved 2 December 2016.
- ^ a b Knuth, Donald E. (1981), "3.3.4: The Spectral Test", The Art of Computer Programming volume 2: Seminumerical algorithms (2nd ed.), Addison-Wesley.
- ^ IBM, System/360 Scientific Subroutine Package, Version II, Programmer's Manual, H20-0205-1, 1967, p. 54.
- ^ International Business Machines Corporation (1968). "IBM/360 Scientific Subroutine Package (360A-CM-03X) Version III" (PDF). Stan's Library. II. White Plains, NY: IBM Technical Publications Department: 77. doi:10.3247/SL2Soft08.001. Scientific Application Program H20-0205-3.
- ^ a b c d e f g Steele, Guy L. Jr.; Vigna, Sebastiano (February 2022) [15 January 2020]. "Computationally easy, spectrally good multipliers for congruential pseudorandom number generators" (PDF). Software: Practice and Experience. 52 (2): 443–458. arXiv:2001.05304. doi:10.1002/spe.3030. Associated software and data at https://github.com/vigna/CPRNG.
- ^ L'Ecuyer, Pierre (January 1999). "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure" (PDF). Mathematics of Computation. 68 (225): 249–260. Bibcode:1999MaCom..68..249L. CiteSeerX 10.1.1.34.1024. doi:10.1090/S0025-5718-99-00996-5. Be sure to read the Errata as well.
- ^ Marsaglia, GEORGE (1972-01-01), Zaremba, S. K. (ed.), "The Structure of Linear Congruential Sequences", Applications of Number Theory to Numerical Analysis, Academic Press, pp. 249–285, ISBN 978-0-12-775950-0, retrieved 2024-01-29
Further reading
[edit]- Entacher, Karl (January 1998). "Bad subsequences of well-known linear congruential pseudorandom number generators". ACM Transactions on Modeling and Computer Simulation. 8 (1): 61–70. doi:10.1145/272991.273009. – lists the (notated as in this text) of many well-known LCGs
- An expanded version of this work is available as: Entacher, Karl (2001). "A Collection of Selected Pseudorandom Number Generators With Linear Structures - extended version".