## 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.