TAOCP 3.2.2 Exercise 9
The modified middle-square method (4) is defined by the recurrence \[ X_{n+1} = (X_n^2 + X_n) \bmod 2^e, \] where \(X_n\) is an integer with \(0 \le X_n < 2^e\).
Exercise 9. [M24] (R. R. Coveyou.) Use the result of exercise 8 to prove that the modified middle-square method (4) has a period of length $2^{e-2}$.
Verified: yes
Solve time: 31m29s
Solution
The modified middle-square method (4) is defined by the recurrence
[
X_{n+1} = (X_n^2 + X_n) \bmod 2^e,
]
where (X_n) is an integer with (0 \le X_n < 2^e). (This is equivalent to the description using (Y_n = 2^e X_n): (Y_{n+1}) is the middle (2e) digits of (Y_n^2 + 2^e Y_n), and (X_{n+1}) is the low (e) bits of (Y_{n+1}).)
We prove that this recurrence possesses a cycle of length exactly (2^{e-2}).
Step 1: Parity and invariance modulo 4.
For any integer (x), (x(x+1)) is even. Hence if (X_0) is odd, (X_1) is even; thereafter all terms are even. Moreover,
[
X_{n+1} \equiv X_n(X_n+1) \pmod{4}.
]
If (X_n \equiv 0 \pmod{4}) then (X_{n+1} \equiv 0 \pmod{4}); if (X_n \equiv 2 \pmod{4}) then (X_{n+1} \equiv 2 \cdot 3 \equiv 2 \pmod{4}). Thus the residue class modulo (4) is invariant once the sequence becomes even. In particular, the set
[
S = { X \in [0,2^e) \mid X \equiv 2 \pmod{4} }
]
is closed under the recurrence. This set has exactly (2^{e-2}) elements.
Step 2: Reduction to a quadratic congruential generator.
For (X_n \in S) write (X_n = 4 Z_n + 2) with (Z_n \in [0, 2^{e-2})). Substituting into the recurrence:
[
\begin{aligned}
4 Z_{n+1} + 2 &= (4 Z_n + 2)^2 + (4 Z_n + 2) \pmod{2^e} \
&= 16 Z_n^2 + 16 Z_n + 4 + 4 Z_n + 2 \pmod{2^e} \
&= 16 Z_n^2 + 20 Z_n + 6 \pmod{2^e}.
\end{aligned}
]
Subtracting (2) and dividing by (4) (which is legitimate because all terms are multiples of (4) and the modulus becomes (2^{e-2})) gives
[
Z_{n+1} = 4 Z_n^2 + 5 Z_n + 1 \pmod{2^{e-2}}.
]
This is a quadratic congruential sequence of the form (3) in the text with
[
m = 2^{e-2}, \qquad d = 4, \qquad a = 5, \qquad c = 1.
]
Step 3: Application of Exercise 8.
Exercise 8 states that a quadratic congruential sequence (Z_{n+1} = d Z_n^2 + a Z_n + c \pmod{m}) has period (m) if and only if:
- (c) is relatively prime to (m);
- (d) and (a-1) are multiples of every odd prime dividing (m);
- If (m) is a multiple of (4): (d) is even and (d \equiv a-1 \pmod{4}); if (m) is a multiple of (2) but not (4): (d \equiv a-1 \pmod{2});
- (d \not\equiv 3c \pmod{9}) if (9 \mid m).
We verify these conditions for our parameters:
- (c = 1) is odd, hence coprime to (m = 2^{e-2}).
- (m) is a power of (2), so there are no odd prime divisors; condition 2 holds vacuously.
- If (e \ge 4) then (m) is a multiple of (4). Here (d = 4) (even) and (a-1 = 4). Both are congruent to (0) modulo (4), so (d \equiv a-1 \pmod{4}). If (e = 3) then (m = 2); the condition reduces to (d \equiv a-1 \pmod{2}), which holds because (4 \equiv 4 \equiv 0 \pmod{2}).
- (m) is not a multiple of (9) (it is a power of (2)), so condition 4 is irrelevant.
All conditions of Exercise 8 are satisfied. Therefore the sequence (\langle Z_n \rangle) has period exactly (m = 2^{e-2}).
Step 4: Conclusion for the original sequence.
The mapping (X_n = 4 Z_n + 2) is a bijection between (\mathbb{Z}/2^{e-2}\mathbb{Z}) and the set (S). Hence the original sequence (\langle X_n \rangle), when restricted to (S), also has period (2^{e-2}). For (e = 2) the formula gives period (1), which is easily verified directly (the only element of (S) is (2), and (2^2+2 \equiv 2 \pmod{4})).
Thus the modified middle-square method (4) possesses a cycle of length (2^{e-2}). ∎
Notes
The proof shows that the maximal period is achieved for any initial value (X_0 \equiv 2 \pmod{4}) (and also for odd (X_0 \equiv 1 \pmod{4}), which map into this cycle after one step). The transformation (X_n = 4Z_n+2) reduces the problem to a quadratic congruential generator that meets the full‑period criteria of Exercise 8, making the result a direct application of that theorem.