homediscover ncsapartnershipsoutreachsoftware_tech
next up previous
Next: Combination Generator Up: Methods for Random Number Previous: Lagged-Fibonacci Generators

Inversive Congruential Generators

An important new type of PRNG that, as yet, has not found any widely distributed implementation is the Inversive Congruential Generator (ICG). This generator comes in two versions, the recursive ICG [30, 31]
and the explicit ICG [32]
In both the above equations tex2html_wrap_inline1561 denotes the multiplicative inverse modulo m in the sense that tex2html_wrap_inline1565 when tex2html_wrap_inline1567, and tex2html_wrap_inline1569.

An advantage of ICGs over LCGs are that tuples made from ICGs do not fall in hyper-planes [33, 34]. Unfortunately the cost of doing modular inversion is considerable: it is tex2html_wrap_inline1571 times the cost of multiplication.

The National Center for Supercomputing Applications

University of Illinois at Urbana-Champaign


Last modified: September 16, 1997