Geradores congruentes lineares

Mapa de retorno tridimensional para RANDU

Um gerador congruencial linear (do inglês Linear congruential generator) ou ainda conhecido pela sigla LCG é um algoritmo que produz uma sequência de números pseudo-aleatório calculados com uma função linear em trecho. O método representa um dos algoritmos de gerador de números pseudo-aleatórios mais antigos e mais conhecidos. A teoria por tras dele é relativamente facil de compreender, sua implementação é simples e sua execução rapida.

O gerador é definido pela relação de recorrência:

$X_{n+1}=\left(aX_{n}+c\right)~~{\bmod {~}}~m$ onde:

• $X$ é a sequencia de valores pseudo-aleatórios,
• $m$ é o módulo, sendo $0<m$,
• $a$ é o multiplicador, sendo $0<a<m$,
• $c$ é o incremento, sendo $0\leq c<m$,
• $X_{0}$ é a semente ou valor inicial, sendo $0\leq X_{0}<m$.

A semente são inteiros constantes que definem o gerador. Se $c=0$, o gerador é comumente chamado de Gerador Congruencial Multiplicativo (do inglês multiplicative congruential generator), geralmente referenciado pela sigla MCG, ou Lehmer RNG. Caso $c\neq 0$ o método é chamado de Gerador Congruencial Misto.

Tamanho do período

O período de um gerador congruencial misto é no máximo $m$ e dependo da escolha do fator $a$ pode ser ainda menor que o modulo. Quando um gerador possui um período completo, todos os valores de $0$ a $m-1$ serão gerados, após $m$ números gerados os valores começam a se repetir gerando um ciclo. O gerador só possuirá um período completo para todas as sementes se e somente se:

1. o modulo $m$ e o incremento $c$ forem relativamente primos,
2. $a-1$ for divisivel por todos os fatores primos de $m$,
3. $a-1$ for divisível por 4 se $m$ for divisível por 4.

Estes três requisitos são definidos como o Teorema de Hull-Dobell. Enquanto LCGs são capazes de produzir números pseudo-aleatórios que passam em um teste de aleatoriedade, isto é extremamente dependente a escolha dos parâmetros $c$, $m$ e $a$.

Historicamente, escolhas ruins levaram a implementações ineficientes dos LCGs. Um exemplo disto é o RANDU, que foi muito utilizado no inicio da década de 70 o que levou a diversos resultados serem questionados.

Exemplo de código

Python

def lcg(modulo, a, c, semente=None):
    if semente != None:
        lcg.anterior = semente
    num_aleatorio = (lcg.anterior * a + c) % modulo
    lcg.anterior = num_aleatorio
    return num_aleatorio
lcg.anterior = 2222