TAOCP 3.3.4 Exercise 20

Let $X_{n+1} \equiv aX_n \pmod{2^e}, \qquad X_0 \text{ odd}, \qquad a \equiv 3 \text{ or } 5 \pmod 8.$ By exercise 3.

taocpmathematicsalgorithmsvolume-2math-medium

Section 3.3.4: The Spectral Test

Exercise 20. [M23] Discuss how to carry out an appropriate spectral test for linear congruential sequences having $c = 0$, $X_0$ odd, $m = 2^e$, $a \bmod 8 = 3$ or $5$. (See exercise 3.2.1.2–9.)

Verified: yes
Solve time: 1m31s

Solution

Let

$X_{n+1} \equiv aX_n \pmod{2^e}, \qquad X_0 \text{ odd}, \qquad a \equiv 3 \text{ or } 5 \pmod 8.$

By exercise 3.2.1.2-9, the odd residues modulo $2^e$ form a cycle of length

$m = 2^{e-2}.$

Hence the sequence runs through all odd residues modulo $2^e$, and the points used in the spectral test are

$\left{\frac1{2^e}(x,ax,a^2x,\ldots,a^{t-1}x)\bmod1 ;\middle|; x \text{ odd}\right}. \eqno(1)$

The ordinary theory in Section 3.3.4 assumes either a full-period mixed generator modulo $m$, or a prime modulus multiplicative generator together with the extra point $(0,\ldots,0)$. Neither hypothesis applies directly here, because only the odd residue classes occur.

We therefore reformulate the test so that the relevant lattice corresponds exactly to the set of attainable points.

For every odd integer $x$ write

$x = 2y+1, \qquad 0 \le y < 2^{e-1}.$

Then

$a^k x = a^k(2y+1)=2a^k y+a^k.$

Hence the $t$-tuples (1) become

\frac{2y+a^0}{2^e}, \frac{2ay+a^1}{2^e}, \ldots, \frac{2a^{t-1}y+a^{t-1}}{2^e} \right). \eqno(2)$$ Since translation does not affect distances between parallel hyperplanes, the constants $a^k/2^e$ are irrelevant for the spectral test. Thus the geometry is identical to that of $$\left{ \frac{y}{2^{e-1}} (1,a,a^2,\ldots,a^{t-1}) \bmod1 ;\middle|; 0 \le y < 2^{e-1} \right}. \eqno(3)$$ The sequence (3) contains each point twice, because the original period length is only $2^{e-2}$. Indeed, $$a^{2^{e-3}} \equiv 1+2^{e-1} \pmod{2^e},$$ therefore $$a^{2^{e-3}}x \equiv x+2^{e-1} \pmod{2^e}$$ for odd $x$, and division by $2^e$ identifies the two corresponding points modulo $1$. Consequently the effective point set has cardinality $2^{e-2}$, exactly as expected. The proper spectral test is therefore obtained by replacing the original odd-residue sequence with the equivalent lattice generated by $$\frac1{2^{e-1}}(1,a,a^2,\ldots,a^{t-1}). \eqno(4)$$ The associated dual lattice consists of all integer vectors $(u_1,\ldots,u_t)$ satisfying $$u_1+au_2+\cdots+a^{t-1}u_t \equiv 0 \pmod{2^{e-1}}. \eqno(5)$$ Equation (5) replaces equation (15) of Section 3.3.4. The spectral accuracy is therefore $$\nu_t^2 = \min \left{ u_1^2+\cdots+u_t^2 ;\middle|; (u_1,\ldots,u_t)\ne(0,\ldots,0), ; u_1+au_2+\cdots+a^{t-1}u_t \equiv0\pmod{2^{e-1}} \right}. \eqno(6)$$ Thus the appropriate procedure is exactly Algorithm S applied with modulus $$m'=2^{e-1},$$ even though the actual period length is only $2^{e-2}$. This reformulation measures the spacing of hyperplanes containing all attainable vectors of successive pseudorandom numbers, and it correctly ignores the impossible even residue classes. The resulting values of $\nu_t$ give the effective accuracy of the multiplicative generator on the odd residues modulo $2^e$. The test also explains the well-known weakness of such generators in low-order bits. Since every $X_n$ is odd, $$X_n \equiv 1 \pmod2,$$hence the least significant bit is constant. More generally, modulo $2^k$ the sequence can occupy at most $2^{k-2}$ residue classes, not $2^k$. The spectral test based on (5) measures precisely the geometric consequences of these restrictions. This completes the proof. ∎