TAOCP 3.2.2 Exercise 25
An alternative to Program A that updates all 55 entries of the $Y$ table every 55th output can be implemented by performing a full sweep of the table instead of a single additive step.
Exercise 25. [**] $[26]$ Discuss the alternative to Program A that changes all 55 entries of the $Y$ table every 55th time a random number is required.
Verified: yes
Solve time: 1m23s
An alternative to Program A that updates all 55 entries of the $Y$ table every 55th output can be implemented by performing a full sweep of the table instead of a single additive step. Specifically, suppose that after generating 54 numbers using the standard cyclic update $Y[k] \leftarrow (Y[k] + Y[j]) \bmod 2^e$, we compute the 55th number by replacing each $Y[i]$ simultaneously with $Y[i] \leftarrow (Y[i] + Y[i-31]) \bmod 2^e$ (indices interpreted modulo 55), and then output one of these new values. This procedure ensures that every entry participates in both addition and output, so the table is refreshed entirely.
The advantage of this approach is that correlations arising from the repeated use of the same table entries are reduced, but the cost is that 55 replacement operations are required for every 55th number instead of just one, so the average number of additions per generated number increases from 1 to 2. This tradeoff is acceptable when stronger mixing of the table entries is desired, especially for long sequences used in high-precision simulations. The period length remains essentially the same, but the statistical properties of the output are slightly improved due to the more uniform refresh of the $Y$ array.
This completes the proof.
∎