Spectral test

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).^[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. The spectral test compares the distance between these planes; the further apart they are, the worse the generator is.^[2] 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,^[3] this is by far the most powerful test known, because it can fail LCGs which pass most statistical tests. The IBM subroutine RANDU^[4]^[5] LCG fails in this test for 3 dimensions and above.

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

^ Williams, K. B.; Dwyer, Jerry (1 Aug 1996), "Testing Random Number Generators, Part 2", Dr. Dobb's Journal, retrieved 26 Jan 2012.
^ Jain, Raj. "Testing Random-Number Generators (Lecture)" (PDF). Washington University Saint Louis. Retrieved 2 December 2016.
^ Knuth, Donald E. (1981), The Art of Computer Programming volume 2: Seminumerical algorithms (2nd ed.), Addison-Wesley, p. 89.
^ IBM, System/360 Scientific Subroutine Package, Version II, Programmer's Manual, H20-0205-1, 1967, p. 54.
^ IBM/360 Scientific Subroutine Package (360A-CM-03X) Version III (PDF). White Plains, NY: IBM Technical Publications Department. 1968. p. 77. doi:10.3247/SL2Soft08.001. Scientific Application Program H20-0205-3.

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

[1] Williams, K. B.; Dwyer, Jerry (1 Aug 1996), "Testing Random Number Generators, Part 2", Dr. Dobb's Journal, retrieved 26 Jan 2012.

[2] Jain, Raj. "Testing Random-Number Generators (Lecture)" (PDF). Washington University Saint Louis. Retrieved 2 December 2016.

[3] Knuth, Donald E. (1981), The Art of Computer Programming volume 2: Seminumerical algorithms (2nd ed.), Addison-Wesley, p. 89.

[4] IBM, System/360 Scientific Subroutine Package, Version II, Programmer's Manual, H20-0205-1, 1967, p. 54.

[5] IBM/360 Scientific Subroutine Package (360A-CM-03X) Version III (PDF). White Plains, NY: IBM Technical Publications Department. 1968. p. 77. doi:10.3247/SL2Soft08.001. Scientific Application Program H20-0205-3.

[1]

[2]

[3]

[4]

[5]