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)¹. 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:

with suitable parameters, it passes statistical tests that LCG generators fail²;
if b is made to be a power of 2 half the size of a register (or half the integer size over which we can conveniently perform arithmetic), then the division and mod operations become trivial;
with this configuration (b a power of 2), the period is not exactly a power of 2, an interesting property for use in combined random number generators.

MWC with b = 2³²

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 2³². This then gives us the very convenient properties:

when we mutliply by a, the carry will end up in the top 32 bits, and the "new value of x" will end up in the lower 32 bits— hence, we don't need two separate variables;
to divide by b (to get the carry), we simply shift 32 bits to the right;
to perform mod b, we simply AND with 2³²-1 (or cast to an int) to get the bottom 32 bits.

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 2⁶³.

Complimentary Multiply with Carry (CMWC)

A common variant of MWC is to pick b = 2³²-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:

it is possible to find values of a for which the generator has a full period of ab + 1, or more precisely, ab^r + 1, where r is the length of lag or "history buffer" applied to the generator;
CMWC also gets round the problem of certain weak seeds that must be avoided with MWC (see Marsaglia (2003) for gory mathematical details³);
with a bit of jiggery-pokery, performing modulo and division by 2³²-1 is almost as easy as with 2³² (we essentially perform it with 2³², then "mop up the difference").

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 = 2³².
3. Marsaglia, G. (2003), "Random Number Generators", Journal of Modern Applied Statistical Methods, 2(1):2-13.

Multiply-with-carry (MWC) random number generators

MWC with b = 232

Complimentary Multiply with Carry (CMWC)

MWC with b = 2³²