49.2.2 Multiply with carry

Multiply–with–carry (MWC) is a method invented by George Marsaglia for generating sequences of pseudo–random integers based on an initial set of from two to many thousands of randomly chosen seed values¹².

The main advantage of the MWC method is that it invokes simple computer integer arithmetic and leads to very fast generation of sequences of pseudo–random numbers with immense periods, ranging from around 260 to 22e6. As with most PRNGs, the resulting sequences are functions of the randomly chosen seed values, but MWC generators seem to behave as well as, and often better than, others in tests of randomness.

A MWC sequence is based on arithmetic modulo M, usually 2^{32}, because arithmetic modulo that M is automatic in most computers, but sometimes a modulo such as 32^2 - 1 is used, because arithmetic for modulus 2^{32} - 1 requires only a simple adjustment from that for 2^{32}, and theory for MWC sequences based on modulus 2^{32} has some nagging difficulties that use of 2^{32} - 1 avoids.

Complementary–multiply–with–carry generators (CMWC) are a slightly modified form of MWC giving better results. A basic formulation of the algorithm uses the recurrence:

N' = (M - 1) - (a * N + C) mod M    0 <= N < M

           a * N + C
C' = floor ---------                     C < a
               M

to generate a new number N' and a new carry C' from an initial state N and an initial carry C, a being the recursion coefficient and M being the modulo.

Better formulations adopt a “lag” of r values: Chosen a positive integer r, an initial carry C and a vector [N(1), N(2), ..., N(r)] of initial seed values, the new number N' and the new carry C' are computed using the seed N(r) as:

N' = (M - 1) - (a * N(r) + C) mod M

           a * N(r) + C
C' = floor ------------
                M

then the seed vector is right–shifted purging N(r):

N(r)   = N(r-1)
N(r-1) = N(r-2)
...
N(2)   = N(1)
N(1)   = N'