Gerador Aleatório MWC

O Gerador de números pseudo-aleatórios chamado Multiply-with-Carry (MWC) foi inventado por George Marsaglia com o propósito de gerar sequências de inteiros aleatórios com grandes períodos. (Marsaglia, 1991) Ele usa um conjunto inicial de sementes de dois a muitos milhares de valores escolhidos aleatoriamente. As principais vantagens do método MWC são que ele invoca a aritmética de inteiros de computador simples e leva à geração muito rápida de sequências de números aleatórios. MWC tem períodos imensos, variando de cerca de 260 a 2 à potência de 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.

Exemplo em Python

Exemplo com 1 milhão de sorteios

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

Veja Também

• Gerador Congruencial Linear