Hello,
There is a technique for implementing a multiplicative linear congruential random number generator
x[n+1] = ( a * x[n] ) mod m (eq. 1)
in 32 bit integers that eliminates the potential for overflow in the intermediate product (a * x[n]), known as Schrage's method, and popularized in Numerical Recipes in C
http://www.library.cornell.edu/nr/bookcpdf/c7-1.pdf Briefly:
*********************************
Schrage�s algorithm is based on an approximate factorization of m,
m = aq + r, i.e., q = [m/a], r = m mod a (7.1.4)
with square brackets denoting integer part. If r is small, specifically
r < q, and 0 < z < m - 1,
it can be shown that both a(z mod q) and r[z/q]lie in the range
0,...,m - 1, and that
az mod m = a(z mod q) - r[z/q] if it is = 0, (7.1.5)
a(z mod q) - r[z/q] + m otherwise
********************************
Applying Schrage to the LCG, in C code, Numerical Recipes achieves
x = a * (x - (x / q) q) - r (x / q) (eq. 2)
by substituting the modulo arithmetic equivalence
x mod q = x - q[x/q]
into a preceding step, which is
x = a * (x % q) - r * (x / q) (eq. 3)
which you get by applying Numerical Recipe's (7.1.5) to the LCG (eq. 1)
So, why keep going past (eq. 3) ??
Doing so replaces the mod operator in (eq. 3) with a subtraction, a multiplication, and a division, in (eq. 2).
Is mod that expensive??
Which expression is faster in
Java? Note that this code can be iterated up to near 10^18 repetitions, with a combined pair of certain such LCGs, so every cycle counts bigtime.
Thanks!!
Paul