Lesson plan

Spectral test

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

Back to article

Article summary

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

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.