Spectral test

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 ${\displaystyle u_{1},u_{2},\dots }$. Let ${\displaystyle 1/\nu _{t}}$ be the maximal separation between covering parallel planes of the sequence ${\displaystyle \{(u_{n+1:n+t})\mid n=0,1,\dots \}}$. The spectral test checks that the sequence ${\displaystyle \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. $${\displaystyle {\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 ${\displaystyle m}$ is the modulus of the LCG.