Multiply-with-carry (MWC) random number generators

The multiply-with-carry (MWC) method is a variant of the add-with-carry generator introduced by Marsaglia and Zaman (1991)1. In its simplest form, MWC uses a similar formula to the linear congruential generator, but with c (the "addend") varying on each iteration. Recall that the LCG formula would normally be the following, with a fixed c (and values chosen for a, c and m that are found to give "good results"):

x <- (a * x + c) mod m

With the MWC algorithm, when we perform the modulo operation to calculate the result to return, the quotient becomes the next value for c.

(1) t <- a * x + c (2) x <- t mod b (3) c <- (int) (t / b)

Interesting properties of the MWC algorithm include the following:

MWC with b = 232

In practice, by far the most convenient application of MWC is to use 64-bit arithmetic (i.e. a Java long), and make the "base" (b) be half of that size, or 232. This then gives us the very convenient properties:

A value of a is chosen so that both ab - 1 and (ab - 1) / 2 are prime; the period is then (ab - 1) / 2.

In Java, this gives us the following MWC implementation, using the first value of a suggested in Numerical Recipies (p. 348: see footnote 2):

final long a = 0xffffda61L;
long x = System.nanoTime() & 0xffffffffL;

public int nextInt() {
  x = (a * (x & 0xffffffffL)) + (x >>> 32);
  return (int) x;
}

This method will produce integers with reasonable randomness, and with a period of around 263.

Complimentary Multiply with Carry (CMWC)

A common variant of MWC is to pick b = 232-1 and use the mofied formula:

(1) t <- a * x + c (2) x <- t mod b (3) x = (b-1) - x (4) c <- (int) (t / b)

With this modified formula:

On the other hand, if used in a combined generator, it's not clear that the weaknesses of the simpler MWC generator are such a problem.


1. See Marsaglia, G. & Zaman, A. (1991), "A New Class of Random Number Generators", The Annals of Applied Probability, 1(3):426-480.
2. For example, the Numerical Recipes authors report values for a that pass the Diehard test with b = 232.
3. Marsaglia, G. (2003), "Random Number Generators", Journal of Modern Applied Statistical Methods, 2(1):2-13.