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.


If you enjoy this Java programming article, please share with friends and colleagues. Follow the author on Twitter for the latest news and rants.

Editorial page content written by Neil Coffey. Copyright © Javamex UK 2021. All rights reserved.