Geradores congruentes lineares 📖 Wikipedia

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.^[1] 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:

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

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

A semente são inteiros constantes que definem o gerador. Se ${\displaystyle 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 ${\displaystyle c\neq 0}$ o método é chamado de Gerador Congruencial Misto.^[2]

O período de um gerador congruencial misto é no máximo ${\displaystyle m}$ e dependo da escolha do fator ${\displaystyle a}$ pode ser ainda menor que o modulo. Quando um gerador possui um período completo, todos os valores de ${\displaystyle 0}$ a ${\displaystyle m-1}$ serão gerados, após ${\displaystyle 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:^[2]

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

Estes três requisitos são definidos como o Teorema de Hull-Dobell.^[3][4] 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 ${\displaystyle c}$, ${\displaystyle m}$ e ${\displaystyle 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.

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

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e

• Portal da matemática