homediscover ncsapartnershipsoutreachsoftware_tech
searchspotlightadv_computingsciencedivisions
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]
 equation1306
and the explicit ICG [32]
 equation1308
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.





NCSA
The National Center for Supercomputing Applications

University of Illinois at Urbana-Champaign

ashoks@ncsa.uiuc.edu

Last modified: September 16, 1997