Schrage's Method




excerpted (pdf) from Numerical Recipes in C by William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling


so, applying the above to the multiplicative LCG

Xi+1 = ( a * Xi ) mod m

or more specifically, to the multiplicative LCG in Java

x = ( a * x ) % m;

gives

q = m / a;
r = m % a;
x = a * (x % q) - r * (x / q);

from Schrage, and, continuing, gives

q = m / a;
r = m % a;
x = a * (x - (x / q) * q) - r * (x / q);

from the modulo arithmetic equivalence between

x mod q

and

x - q[x/q]

and finally, adding Schrage's 'otherwise' clause gives

(1)   q = m / a;
(2)   r = m % a;

(3)   x = a * (x - (x / q) * q) - r * (x / q);
(4)   if (x < 0) x += m;

Statements (1) and (2) evaluate once, at sequence initilization.

Statement (3), and, conditionally, statement (4), evaluate at each rand request.