
Java tutorials home
java.util.Random
Random number generators
XORShift
High quality random
Seeding generators
Entropy
SecureRandom
Random sampling
Random simulations and nextGaussian()
Multiplywithcarry (MWC) random number generatorsThe multiplywithcarry (MWC) method is a variant of the addwithcarry 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.
Interesting properties of the MWC algorithm include the following:
MWC with b = 2^{32}In practice, by far the most convenient application of MWC is to use 64bit 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:
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}. Complimentary Multiply with Carry (CMWC)A common variant of MWC is to pick b = 2^{32}1 and use the mofied formula:
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):426480. Written by Neil Coffey. Copyright © Javamex UK 2013. All rights reserved. 