In computer science, multiply-with-carry (MWC) is a method invented by George Marsaglia[1] for generating sequences of random integers based on an initial set from two to many thousands of randomly chosen seed values.
The main advantages of the MWC method are that it invokes simple computer integer arithmetic and leads to very fast generation of sequences of random numbers with immense periods, ranging from around
As with all pseudorandom number generators, the resulting sequences are functions of the supplied seed values.
Normal Lehmer generator implementations choose a modulus close to the machine word size.
is typically chosen to equal the computer's word size, as this makes arithmetic modulo
Although the theory of MWC generators permits a > b, a is almost always chosen smaller for convenience of implementation.
This discards the least significant word of zero (which, in practice, is never computed at all) and effectively multiplies the state by b−1 (mod p).
This is the same as a generator with multiplier b, but producing output in reverse order, which does not affect the quality of the resultant pseudorandom numbers.
However, many microprocessors can compute a full 64-bit product in almost the same time as the low 32 bits.
With multiplier a specified, each pair of input values x, c is converted to a new pair, If x and c are not both zero, then the period of the resulting multiply-with-carry sequence will be the order of b = 232 in the multiplicative group of residues modulo abr − 1, that is, the smallest n such that bn ≡ 1 (mod abr − 1).
In such a case, for b= 232 and r = 1, the period will be abr/2 − 1, approaching 263, which in practice may be an acceptably large subset of the number of possible 32-bit pairs (x, c).
More specifically, in such a case, the order of any element divides p − 1, and there are only four possible divisors: 1, 2, abr/2 − 1, or abr − 2.
Following are some maximal values of a for computer applications which satisfy the above safe prime condition, for lag-1 generators: While a safe prime ensures that almost any element of the group has a large order, the period of the generator is specifically the order of b.
For small moduli, more computationally expensive methods can be used to find multipliers a where the period is ab/2 − 1.
The output of a multiply-with-carry generator is equivalent to the radix-b expansion of a fraction with denominator p = abr − 1.
Consider just the sequence of xi: Notice that if those repeated segments of x values are put in reverse order: we get the expansion j/(ab−1) with a=7, b=10, j=10: This is true in general: The sequence of xs produced by a lag-r MWC generator: when put in reverse order, will be the radix-b expansion of a fraction j/(abr − 1) for some 0 < j < abr.
This is true in general, (but apparently only for lag-1 MWC sequences[citation needed]): Given initial values
Establishing the period of a lag-r MWC generator usually entails choosing multiplier a so that p = abr − 1 is prime.
This leads to a slight modification of the MWC procedure, and produces a modulus p = |−abr − 1| = abr + 1.
The modified procedure is called complementary-multiply-with-carry (CMWC), and the setup is the same as that for lag-r MWC: multiplier a, base b, and r + 1 seeds, The modification is to the generation of a new pair (x, c).
Rearranging the computation to avoid negative numbers, the new x value is complemented by subtracting it from b − 1: The resulting sequence of x's produced by the CMWC RNG will have period the order of b in the multiplicative group of residues modulo abr+1, and the output x's, in reverse order, will form the base b expansion of j/(abr+1) for some 0 < j < abr.
Use of lag-r CMWC makes it much easier to find periods for r's as large as 512, 1024, 2048, etc.
Another advantage of this modified procedure is that the period is a multiple of b, so the output is exactly equidistributed mod b.
One disadvantage of the CMWC construction is that, with a power-of-two base, the maximum achievable period is less than for a similar-sized MWC generator; you lose several bits.
First, it is possible to add additional terms to the product, producing a modulus of the form arbr+asbs−1.
However, this does not fix the period issue, which depends on the low bits of the modulus.
Goresky and Klapper[5] developed the theory of these generalized multiply-with-carry generators, proving, in particular, that choosing a negative a0 and ar–a0 < b the carry value is always smaller than b, making the implementation efficient.
The more general form of the modulus improves also the quality of the generator, albeit one cannot always get full period.
To implement a Goresky-Klapper generator one precomputes a−10 (mod b), and changes the iteration as follows:[6] In the common case that b = 2k, a0 must be odd for the inverse to exist.
The following are implementations of small-state Goresky-Klapper's generalized MWC generators with 64-bit output using 128-bit multiplications.