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]

O multiplicador é representado por a, enquanto o módulo é representado por b. Existe uma variável adicional c, que representa o transporte. O cálculo do transporte é mostrado na Equação abaixo. MWC Calcular C...

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

A variável n representa o número na sequência que você está calculando. É importante que n seja sempre maior que r. Isso ocorre porque os valores de x antes de n são os valores de sementes e temos r sementes.

O gerador MWC tem um período muito maior do que LCG e suas implementações são normalmente muito rápidas de executar. É uma melhoria em relação ao LCG, mas não é um gerador comumente usado. Não é o gerador de números aleatórios padrão para nenhuma linguagem de computador que eu conheça.

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

• Gerador Congruencial Linear