Next: Tausworthe Generators
Up: Random Number Generators
Previous: Linear 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:
where
if and
. To
calculate , one can apply the reverse of Euclid's algorithm to
find integer solutions for
.
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 longrange 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. .
Figure 3:
Twodimensional plot of (,) produced by ICG.
The parameters are and .

Next: Tausworthe Generators
Up: Random Number Generators
Previous: Linear Congruential Generators
20010530