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] LCG fails in this test for 3 dimensions and above.

References

  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.


This article is issued from Wikipedia - version of the 12/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.