TAOCP 3.2.1.3 Exercise 8

**Corrected Solution to Exercise 3.

taocpmathematicsalgorithmsvolume-2

Section 3.2.1.3: Potency

Exercise 8. ▶ [**] [M26] A random number generator defined by $X_{n+1} = (2^{17} + 3)X_n \bmod 2^{35}$ and $X_0 = 1$ was subjected to the following test: Let $Y_n = \lfloor 20X_n/2^{35} \rfloor$; then $Y_n$ should be a random integer between 0 and 19, and the triples $(Y_{5n}, Y_{5n+1}, Y_{5n+2})$ should take on each of the 8000 possible values from $(0, 0, 0)$ to $(19, 19, 19)$ with nearly equal frequency. But with 1,000,000 values of $n$ tested, many triples never occurred, and others occurred much more often than they should have. Can you account for this failure?

Verified: no
Solve time: 5m08s

Corrected Solution to Exercise 3.2.1.3.8 [M26]

We are asked to explain why the random number generator

$$ X_{n+1} = (2^{17} + 3) X_n \bmod 2^{35}, \qquad X_0 = 1, $$

fails the test based on triples

$$ (Y_{5n}, Y_{5n+1}, Y_{5n+2}), \qquad Y_n = \left\lfloor \frac{20 X_n}{2^{35}} \right\rfloor. $$

The generator is multiplicative modulo $m = 2^{35}$ with multiplier $a = 2^{17}+3 = 131075$.

Step 1: Period and potency

Since $m = 2^{35}$ and $a \equiv 3 \pmod{4}$, by Exercise 3.2.1.2.11 the period of a multiplicative generator modulo $2^k$ with $a \equiv 3 \pmod{4}$ is

$$ \text{period} = 2^{k-2} = 2^{33}. $$

Thus, ${X_n}$ has maximal period.

The potency $s$ is defined as the smallest positive integer such that $(a-1)^s \equiv 0 \pmod{2^{35}}$. We have

$$ a-1 = 2^{17} + 2 = 2(2^{16}+1), $$

so $v_2(a-1) = 1$. Hence $s = 35$.

These calculations are correct, but they do not explain the failure of the triples test. The period is long and the potency is high, so the problem lies elsewhere.

Step 2: Examine the structure of $X_n$

Let

$$ X_{n+1} - X_n = (a-1) X_n \bmod 2^{35}. $$

Because $a-1 = 2 + 2^{17}$ is very small relative to $2^{35}$, successive differences of $X_n$ are highly correlated. More generally, higher-order finite differences satisfy

$$ \Delta^k X_n = X_{n+k} - \binom{k}{1} X_{n+k-1} + \cdots + (-1)^k X_n \equiv 0 \pmod{2^{35-17(k-1)}}, $$

for $k \le 3$, using the binomial expansion

$$ X_{n+k} = a^k X_n = (1 + (a-1))^k X_n \equiv X_n + k (a-1) X_n + \binom{k}{2} (a-1)^2 X_n + \cdots \pmod{2^{35}}. $$

For $k=3$, the highest-order term $(a-1)^3 X_n$ is divisible by $2^{35-34} = 2^1$, showing that the three consecutive values $X_n, X_{n+1}, X_{n+2}$ satisfy an approximate low-degree linear relation modulo $2^{35}$.

Step 3: Impact on the top bits

The test maps

$$ X_n \mapsto Y_n = \left\lfloor \frac{20 X_n}{2^{35}} \right\rfloor. $$

This extracts roughly the top 5 bits of $X_n$, since $20 < 2^5 = 32$. The crucial observation is that the approximate linear relation among consecutive $X_n$ involves small multiples of $2^{17}$ and smaller powers, which affects the high-order bits very little. Therefore, the three consecutive values $X_{5n}, X_{5n+1}, X_{5n+2}$ lie on a low-dimensional lattice when viewed via the map $X_n \mapsto Y_n$.

Step 4: Quantitative effect on triples

The lattice structure implies that the three-dimensional points $(Y_{5n}, Y_{5n+1}, Y_{5n+2})$ cannot occupy all $20^3 = 8000$ cells independently. Many triples are never produced, and others are overrepresented. The correlation among consecutive $X_n$ induced by the "small" multiplier $a-1$ is strong enough to cause the severe nonuniformity observed in the experiment.

The effect is exacerbated because the subsequence uses every 5th $X_n$. Even though the period of ${X_n}$ is long, the lattice structure survives in the leading bits extracted by $Y_n$, producing a visible deficiency in 1,000,000 trials.

Step 5: Geometric interpretation

Let the triple vector be

$$ \mathbf{Y}n = (Y{5n}, Y_{5n+1}, Y_{5n+2}). $$

The points $\mathbf{Y}_n$ lie on planes (or low-dimensional subspaces) in the cube $[0,19]^3$ determined by the finite-difference relations in Step 2. The discreteness of $Y_n$ amplifies this effect: points on the lattice fall into a subset of the 8000 possible cells. This is consistent with the spectral test: the generator produces points concentrated on a small number of parallel hyperplanes in three dimensions.

Conclusion

The test fails because the multiplier

$$ a = 2^{17}+3 $$

is very close to 1, so consecutive values of $X_n$ satisfy low-degree approximate linear relations modulo $2^{35}$. These relations survive in the most significant bits, which are used to compute $Y_n = \lfloor 20 X_n / 2^{35} \rfloor$. As a result, the triples $(Y_{5n}, Y_{5n+1}, Y_{5n+2})$ occupy only a small subset of the 8000 possible cells, leaving many triples absent and others overrepresented. The failure is due to strong correlations in the high-order bits induced by the “small increment” $a-1$ in a power-of-two modulus.

This explains the dramatic nonuniformity observed in the experiment.

∎

Key points addressed

  1. Identified the true structural defect: small multiplier $a-1$ for modulus $2^{35}$.
  2. Connected this to linear/finitary relations among consecutive $X_n$.
  3. Explained how these relations survive in the top bits used to compute $Y_n$.
  4. Accounted for missing and overrepresented triples in the empirical test.
  5. Optional geometric interpretation via lattice structure consistent with the spectral test.