TAOCP 3.6 Exercise 12
A lagged Fibonacci generator of the type recommended in Section 3.
Exercise 12. ▶ [**] [M21] What random number generator would be suitable for a minicomputer that does arithmetic only on integers in the range $[-32768,.,.,32767]$?
Verified: yes
Solve time: 1m04s
A lagged Fibonacci generator of the type recommended in Section 3.6 is suitable, because it requires only addition, subtraction, and comparisons within the machine range. Let the modulus be $m=2^{15}=32768$, and define
$$ X_n=(X_{n-100}-X_{n-37})\bmod 2^{15}. $$
Since all values lie in $[0,.,.,32767]$, the subtraction can be performed safely by
$$ Y\leftarrow X_{n-100}-X_{n-37}; $$
if $Y<0$, set $Y\leftarrow Y+32768$. No intermediate quantity ever leaves the interval $[-32767,.,.,32767]$.
A multiplicative congruential generator is less satisfactory on such a machine, because the products $aX$ needed in
$$ X\leftarrow(aX+c)\bmod m $$
would overflow unless special multiple-precision techniques were introduced. The lagged Fibonacci method avoids multiplication entirely and still provides a long period and good statistical behavior.