TAOCP 3.2.2 Exercise 1
The recurrence U_{n+1}=(aU_n+c/m)\bmod 1 is mathematically equivalent to the linear congruential generator
Exercise 1. ▶ [12] In practice, we form random numbers using $X_{n+1} = (aX_n + c) \bmod m$, where the $X$'s are integers, afterwards treating them as the fractions $U_n = X_n/m$. The recurrence relation for $U_n$ is actually
$$U_{n+1} = (aU_n + c/m) \bmod 1.$$
Discuss the generation of random sequences using this relation directly, by making use of floating point arithmetic on the computer.
Verified: yes
Solve time: 1m25s
Solution
The recurrence
$$ U_{n+1}=(aU_n+c/m)\bmod 1 $$
is mathematically equivalent to the linear congruential generator
$$ X_{n+1}=(aX_n+c)\bmod m, \qquad U_n=\frac{X_n}{m}, $$
because
$$ aU_n+\frac{c}{m} = \frac{aX_n+c}{m}, $$
and reduction modulo $1$ corresponds exactly to reduction of the numerator modulo $m$.
The question is whether it is advantageous to generate the sequence directly in floating point form.
If floating point arithmetic were exact, there would be no difference. One would store $U_n$ instead of $X_n$, compute
$$ V=aU_n+\frac{c}{m}, $$
and then set
$$ U_{n+1}=V-\lfloor V\rfloor . $$
The difficulty is that floating point numbers form only a finite set. Hence the values of $U_n$ are rounded after each operation. The recurrence actually executed by the machine is therefore
$$ U_{n+1} = \operatorname{fl}!\left( \operatorname{fl}!\left(aU_n+\frac{c}{m}\right) - \Bigl\lfloor \operatorname{fl}!\left(aU_n+\frac{c}{m}\right) \Bigr\rfloor \right), $$
where $\operatorname{fl}$ denotes floating point rounding.
These rounding errors destroy the exact correspondence with the congruence modulo $m$. Two distinct values $X_n$ and $X_n'$ may yield the same floating point value of $U_n$, and a value that should be mapped to one residue class modulo $m$ may be rounded into another. Consequently the actual period and distribution properties become dependent on the details of the floating point representation.
When $m=2^e$ and the floating point fraction contains at least $e$ bits in its mantissa, the situation is better. Every number of the form $X/m$ is then represented exactly. If, in addition, the multiplication by $a$ and the addition of $c/m$ are performed with sufficient precision that no rounding occurs before reduction modulo $1$, the floating point recurrence reproduces the integer generator exactly. Such favorable circumstances are exceptional, because the product $aU_n$ generally requires more precision than is available in a single floating point word.
A direct floating point generator can nevertheless be attractive for additive recurrences such as (7), where only addition modulo $1$ is required. Brent observed that such methods can be implemented correctly in floating point arithmetic because the operation
$$ U_n=(U_{n-24}+U_{n-55})\bmod 1 $$
involves no growth in the number of significant digits. Multiplicative generators are less suitable, since multiplication continually creates digits that must be rounded away.
Therefore the direct recurrence modulo $1$ is theoretically equivalent to the integer congruential method, but in practice it is usually inferior for multiplicative congruential generators. Integer arithmetic preserves the congruence exactly and guarantees the intended period, whereas floating point arithmetic introduces rounding effects that alter the sequence. For this reason random numbers are ordinarily generated as integers and only afterwards converted to the fractions $U_n=X_n/m$.
$$ \boxed{\text{Generate the sequence in integer arithmetic; use the direct floating point form only when exactness can be guaranteed.}} $$