Spectral Test

This test is devised to study the lattice structures of LCGs as mentioned in Section 3.1, so it can not be applied to other families of RNGs. According to Knuth in [8], this is by far the most powerful test known, because it can fail LCGs which pass most statistical tests. The IBM RANDU LCG (with parameters $M=2^{31},A=2^{16}+3,B=0$) fails in this test for 3 dimensions and above (see Figure 2.)

The theory behind the spectral test algorithm is quite complicated; it suffices to say that the goal is to determine the value of

$$\nu_{k} = \min \left\{ \sqrt{x_1^2+x_2^2+\cdots+x_k^2} \right\}$$

subject to

$$x_1+Ax_2+\cdots+A^{k-1}x_k \equiv 0 \mbox{ (mod } M)$$

where $\nu_{k}$ is the inverse of $d_k$. $d_k, A, M$, and $k$ have the same meanings as in Section 3.1.

Any good LCG should have high values for each $\nu_{k}$. Theoretical value of $\nu_{k}$ is $m^{1/k}$ where $m$ is the period length. With spectral test, we can estimate the how worse the lattice structure will be without plotting millions of samples. IBM RANDU LCG has $\nu_2=23169.06$, which is good, but $\nu_3=10.86$, which is much less than theoretical value 812.75. The maximum distance between the hyperplanes in Figure 2 is thus as large as $\frac{1}{10.86}=0.09$.

Our spectral test code is an exact implementation of the algorithm given in [8].