TAOCP 3.2.2 Exercise 3

We first compute the sequences $(X_n)$ and $(Y_n)$ modulo 8, given the recurrences $X_{n+1} = (5X_n + 3) \bmod 8, \quad X_0 = 0,$ $Y_{n+1} = (5Y_n + 1) \bmod 8, \quad Y_0 = 0,$ and $k = 4$.

taocpmathematicsalgorithmsvolume-2medium

Section 3.2.2: Other Methods

Exercise 3. [23] (a) What sequence does Algorithm M generate if

$$X_0 = 0, \quad X_{n+1} = (5X_n + 3) \bmod 8, \quad Y_0 = 0, \quad Y_{n+1} = (5Y_n + 1) \bmod 8,$$

and $k = 4$? (Note that the potency is two, so $(X_n)$ and $(Y_n)$ aren't extremely random to start with.) (b) What happens if Algorithm B is applied to this same sequence $(X_n)$ with $k = 4$?

Verified: yes
Solve time: 1m29s

Solution

We first compute the sequences $(X_n)$ and $(Y_n)$ modulo 8, given the recurrences

$X_{n+1} = (5X_n + 3) \bmod 8, \quad X_0 = 0,$

$Y_{n+1} = (5Y_n + 1) \bmod 8, \quad Y_0 = 0,$

and $k = 4$.

Part (a) Algorithm M

Algorithm M, as defined in Section 3.2.2, maintains an array of length $k$ and at each step outputs the difference modulo $m$ between the current $X_n$ and the $k$-step-back element. With $k = 4$, we must first generate the initial $X_0, X_1, X_2, X_3$:

  1. $X_0 = 0$
  2. $X_1 = (5 \cdot 0 + 3) \bmod 8 = 3$
  3. $X_2 = (5 \cdot 3 + 3) \bmod 8 = (15 + 3) \bmod 8 = 18 \bmod 8 = 2$
  4. $X_3 = (5 \cdot 2 + 3) \bmod 8 = 13 \bmod 8 = 5$
  5. $X_4 = (5 \cdot 5 + 3) \bmod 8 = 28 \bmod 8 = 4$
  6. $X_5 = (5 \cdot 4 + 3) \bmod 8 = 23 \bmod 8 = 7$
  7. $X_6 = (5 \cdot 7 + 3) \bmod 8 = 38 \bmod 8 = 6$
  8. $X_7 = (5 \cdot 6 + 3) \bmod 8 = 33 \bmod 8 = 1$
  9. $X_8 = (5 \cdot 1 + 3) \bmod 8 = 8 \bmod 8 = 0$

Thus the $X_n$ sequence begins:

$0, 3, 2, 5, 4, 7, 6, 1, 0, \dots$

Similarly, for $Y_n$:

  1. $Y_0 = 0$
  2. $Y_1 = (5 \cdot 0 + 1) \bmod 8 = 1$
  3. $Y_2 = (5 \cdot 1 + 1) \bmod 8 = 6 \bmod 8 = 6$
  4. $Y_3 = (5 \cdot 6 + 1) \bmod 8 = 31 \bmod 8 = 7$
  5. $Y_4 = (5 \cdot 7 + 1) \bmod 8 = 36 \bmod 8 = 4$
  6. $Y_5 = (5 \cdot 4 + 1) \bmod 8 = 21 \bmod 8 = 5$
  7. $Y_6 = (5 \cdot 5 + 1) \bmod 8 = 26 \bmod 8 = 2$
  8. $Y_7 = (5 \cdot 2 + 1) \bmod 8 = 11 \bmod 8 = 3$
  9. $Y_8 = (5 \cdot 3 + 1) \bmod 8 = 16 \bmod 8 = 0$

Thus the $Y_n$ sequence begins:

$0, 1, 6, 7, 4, 5, 2, 3, 0, \dots$

Algorithm M outputs $Z_n = X_n - X_{n-k} \bmod 8$. With $k = 4$, the first outputs occur at $n = 4$:

  1. $Z_4 = X_4 - X_0 \bmod 8 = 4 - 0 = 4$
  2. $Z_5 = X_5 - X_1 \bmod 8 = 7 - 3 = 4$
  3. $Z_6 = X_6 - X_2 \bmod 8 = 6 - 2 = 4$
  4. $Z_7 = X_7 - X_3 \bmod 8 = 1 - 5 = -4 \bmod 8 = 4$
  5. $Z_8 = X_8 - X_4 \bmod 8 = 0 - 4 = -4 \bmod 8 = 4$

All subsequent outputs repeat the same pattern because $(X_n)$ is periodic with period 8. Hence Algorithm M generates the constant sequence:

$Z_n \equiv 4 \pmod 8 \quad \text{for } n \ge 4.$

The same applies to the sequence $(Y_n)$ if used in Algorithm M; the output is similarly constant modulo 8.

Part (b) Algorithm B

Algorithm B, described in Section 3.2.2, applies a "mixing" procedure to the original sequence. For small modulus $m = 8$ and $k = 4$, the differences between consecutive $k$-spaced elements are taken modulo $m$. The initial differences in $(X_n)$ are all 4, as shown above. Algorithm B adds further operations, but since $Z_n \equiv 4$ already, the transformations modulo 8 leave the output unchanged. Consequently, applying Algorithm B to $(X_n)$ with $k = 4$ produces the same constant output sequence:

$4, 4, 4, 4, \dots$

The sequences are therefore highly non-random, illustrating that low potency sequences yield poor results under Algorithms M and B.

This completes the solution.

∎