Linear congruential generator modulo a power of two

Let an integer $w\ge 2$, $M=2^w$, integers $a,c$, and a seed $x_0\in \{0,\dots ,M-1\}$ be inputs. For an integer $r$, $[r{]}_M$ denotes the unique residue in $\{0,\dots ,M-1\}$ congruent to $r$ modulo $M$. The state sequence and returned midpoint word are $x_{n+1}=[a{x}_n+c{]}_M,u_n=\frac{x_n+1\mathrm{/}2}{M}(n\ge 0)\mathrm{.}$ The output is the deterministic state sequence, or its midpoint conversion $u_n\in (0,1)$. A full-period LCG is the special case $a\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$ and $c$ odd; its period is proved separately. A seed chosen at random is a distinct probability model, not part of this deterministic procedure.

An LCG has finite state and therefore eventually repeats. Full period and uniform one-time marginals do not assert independence of successive states. The output conversion uses midpoints to avoid exact values $0$ and $1$.