Multiply with Carry Random Generator

The Multiply with Carry (MWC) PRNG was invented by George Marsaglia for the purpose of generating sequences of random integers with large periods. (Marsaglia, 1991) It uses an initial seed set from two to many thousands of randomly chosen 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. MWC has immense periods, ranging from around 260 to 2 to the power of 2000000.

MWC works somewhat similarly to LCG. Assuming 32 bit registers, LCG uses only the lower 32 bits of the multiplication. MWC makes use of these higher bits through a carry. Additionally, multiple seed values are used. These seed values are typically created with another PRNG algorithm, such as LCG.

We must first define a variable r to describe the “lag” of the MWC. We must provide a number of seed values equal to r. Like the LCG algorithm (Equation 4.2), we also have a modulus and a multiplier. However, there is no increment in this case. The equation used to generate the random integers for MWC is shown in Equation below:

[math]x_n = (ax_{n-r}+c_{n-1})~ mod ~ b, n \geq r[/math]

The multiplier is represented by a, while the modulus is represented by b. There is an additional variable c, which represents the carry. The calculation for the carry is shown in Equation below...

[math]c_n = \bigl \lfloor \frac{ax_{n-r}+c_{n-1}}{b} \bigr \rfloor, n \geq r[/math]

The variable n represents the number in the sequence you are calculating. It is important that n always be greater than r. This is because the x values before n are the seed values, and we have r seeds.

The MWC generator has a much larger period than LCG, and its implementations are typically very fast to execute. It is an improvement over LCG, but it is not a commonly used generator. It is not the default random number generator for any computer language that I am aware of.

Sample Python Code

1 million attempts sample

import math
def multiply_with_carry(mult=16807,mod=10,seed=123456789,r=1,size=1):
    
    """
    MWC generator
    """
    C = pseudo_uniform(seed=seed, size=size)
    X = pseudo_uniform(seed=seed, size=size)

    for i in range(r, size):
        X[i] = (mult * X[i - r] + C[i - 1]) % mod
        C[i] = math.floor((mult * X[i - r] + C[i - 1]) / mod)
        
    return X

See Also

• Linear Congruencial Generator