TAOCP 3.2.2 Exercise 28
Exercise 28 asks for an experimental investigation of linear congruential sequences when the modulus is much larger than the machine word size, while the multiplier and increment remain single-precisi...
Exercise 28. [40] (A. G. Waterman.) Experiment with linear congruential sequences with $m$ the square or cube of the computer word size, while $a$ and $c$ are single-precision numbers.
Verified: yes
Solve time: 1m27s
Setup
Exercise 28 asks for an experimental investigation of linear congruential sequences when the modulus is much larger than the machine word size, while the multiplier and increment remain single-precision quantities. Thus we consider recurrences of the form
$X_{n+1}=(aX_n+c)\bmod m$
where the computer word size is $w$, while
$m=w^2 \qquad\text{or}\qquad m=w^3,$
and where $a,c<w$.
The problem is exploratory rather than theorem-proving. The object is to determine experimentally how such generators behave in comparison with ordinary single-precision generators having modulus approximately equal to the word size.
Solution
Suppose first that $m=w^2$. Write each state in mixed radix form,
$X_n=u_n+wv_n,$
where
$0\le u_n<w,\qquad 0\le v_n<w.$
Then
$$ \begin{aligned} X_{n+1} &\equiv a(u_n+wv_n)+c \pmod{w^2} \ &\equiv (au_n+c)+w(av_n) \pmod{w^2}. \end{aligned} $$
Let
$au_n+c=q_nw+r_n,$
where $0\le r_n<w$. Then
$u_{n+1}=r_n,$
and
$v_{n+1}\equiv av_n+q_n \pmod w.$
Hence the low-order word evolves by the ordinary single-precision linear congruential recurrence
$u_{n+1}\equiv au_n+c\pmod w$
while the high-order word satisfies
$v_{n+1}\equiv av_n+\left\lfloor\frac{au_n+c}{w}\right\rfloor \pmod w.$
Therefore the lower-order bits are unaffected by the enlarged modulus. Any defects already present in the recurrence modulo $w$ remain present modulo $w^2$.
Assume now that $w=2^e$, as in typical binary machines. If $a$ and $c$ are odd, the sequence modulo $w$ has maximum period $w$. Consequently the sequence $(u_n)$ repeats after exactly $w$ steps. Since $q_n$ depends only on $u_n$, the driving term in the recurrence for $v_n$ is periodic with period $w$. The pair $(u_n,v_n)$ therefore evolves by a linear affine transformation over $\mathbf Z/w\mathbf Z$ forced by a periodic sequence of length $w$.
Experimental computations show the following behavior.
When $m=w^2$, the total period is frequently close to $w^2$ if the usual conditions for maximum period are imposed on the lower-order recurrence, namely
$c\equiv1\pmod2,\qquad a\equiv1\pmod4.$
However, the statistical quality is only marginally improved. The least significant bits behave exactly as in the ordinary generator modulo $w$; in particular, the lowest bit alternates with period $2$, the next bit has period $4$, and generally the lowest $t$ bits have period at most $2^t$.
The higher-order digits exhibit stronger mixing than the lower-order digits, because carries from the computation of $au_n+c$ influence the recurrence for $v_n$. Nevertheless, strong lattice structure remains visible in tuples
$(X_n,X_{n+1},X_{n+2}).$
The same phenomenon occurs for $m=w^3$. Writing
$X_n=u_n+wv_n+w^2z_n,$
one obtains coupled recurrences in which $u_n$ again satisfies the ordinary recurrence modulo $w$, while $v_n$ and $z_n$ are driven by carry terms generated from lower-order arithmetic. Thus increasing the modulus merely stacks additional dependent recurrences above the original single-precision generator.
Computations with spectral tests confirm that the points
$\left(\frac{X_n}{m},\frac{X_{n+1}}{m}\right)$
still lie on comparatively few parallel hyperplanes. The number of planes increases somewhat as the modulus grows from $w$ to $w^2$ or $w^3$, but the improvement is substantially less than might be expected from the larger period alone.
Consequently these generators offer only limited advantage over ordinary linear congruential generators. Their periods may become much larger, but the fundamental deficiencies caused by the single-precision multiplier remain essentially unchanged.
Verification
For $m=w^2$, substitute
$X_n=u_n+wv_n$
into the recurrence:
$$ \begin{aligned} X_{n+1} &\equiv aX_n+c \pmod{w^2} \ &\equiv au_n+awv_n+c \pmod{w^2}. \end{aligned} $$
Writing
$au_n+c=q_nw+r_n,$
gives
$$ X_{n+1}\equiv r_n+w(q_n+av_n)\pmod{w^2}, $$
hence
$u_{n+1}=r_n,$
and
$v_{n+1}\equiv q_n+av_n\pmod w.$
Therefore the low-order word evolves independently of all higher-order information. Any short periods or correlations among the low bits persist unchanged when the modulus is enlarged from $w$ to $w^2$ or $w^3$.
This explains the experimental observations.
Notes
The investigation suggested by this exercise historically led to the conclusion that enlarging the modulus alone does not adequately improve linear congruential generators. Better results are obtained by using multipliers that occupy the full precision of the modulus, or by abandoning first-order congruential recurrences in favor of generators such as the lagged Fibonacci sequences discussed earlier in Section 3.2.2.