Inversive Congruential Generators

Sometimes the Parallel Hyperplanes phenomenon inherent in LCGs may cause adverse effects to certain simulation applications because the space between the hyperplanes will never be hit by any point of the generator, and the simulation result may be very sensitive to this kind of regularities. Inversive Congruential Generators (ICG) are designed to overcome this difficulty. It is a variant of LCG:

$$x_{n+1} = \overline{(Ax_n + B)} \mbox{ mod } M$$

where $\overline{c} = 0$ if $c=0$ and $\overline{c} = c^{-1} \mbox{ mod } M$. To calculate $\overline{c}$, one can apply the reverse of Euclid's algorithm to find integer solutions for $\overline{c}c + kM = 1$.

Although the extra inversion step eliminates Parallel Hyperplanes (see Figure 3), it also changes the intrinsic structures and correlation behaviors of LCGs [5]. ICGs are promising candidates for parallelization, because unlike LCGs, ICGs do not have long-range autocorrelations problems. However, at current state of the art, ICGs are substantially (8X) slower than LCGs due to the inversion process. ICGs have the same period as their LCG counterparts, i.e. $M-1$.

Figure 3: Two-dimensional plot of ($U_i$,$U_{i+1}$) produced by ICG. The parameters are $M=256$ and $B=2$.