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 funciona de forma semelhante ao LCG. Assumindo registros de 32 bits, o LCG usa apenas os 32 bits inferiores da multiplicação. MWC faz uso desses bits mais altos por meio de um transporte. Além disso, vários valores de semente são usados. Esses valores de semente são normalmente criados com outro algoritmo PRNG, como LCG.

Devemos primeiro definir uma variável r para descrever o “lag” do MWC. Devemos fornecer um número de valores de semente igual a r. Como o algoritmo LCG, também temos um módulo e um multiplicador. No entanto, não há incremento neste caso. A equação usada para gerar os inteiros aleatórios para MWC é mostrada abaixo. Para calcular o número inteiro aleatório (MWC) usamos a equação:

[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