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"):

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
^{2}; - 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.

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^{32}.
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**, we simply*b***AND**with 2^{32}-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^{63}.

A common variant of MWC is to pick *b* = 2^{32}-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*, where^{r}+ 1*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
^{3}); - with a bit of jiggery-pokery, performing modulo and division by 2
^{32}-1 is almost as easy as with 2^{32}(we essentially perform it with 2^{32}, 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^{32}.

3. Marsaglia, G. (2003), "Random Number Generators", *Journal of Modern Applied Statistical Methods*,
2(1):2-13.

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