Geradores congruentes lineares
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Randu2.png/220px-Randu2.png)
O gerador é definido pela relação de recorrência:
onde:
- é a sequencia de valores pseudo-aleatórios,
- é o módulo, sendo ,
- é o multiplicador, sendo ,
- é o incremento, sendo ,
- é a semente ou valor inicial, sendo .
A semente são inteiros constantes que definem o gerador. Se , o gerador é comumente chamado de Gerador Congruencial Multiplicativo (do inglês multiplicative congruential generator), geralmente referenciado pela sigla MCG, ou Lehmer RNG. Caso o método é chamado de Gerador Congruencial Misto.[2]
Tamanho do período
O período de um gerador congruencial misto é no máximo e dependo da escolha do fator
pode ser ainda menor que o modulo. Quando um gerador possui um período completo, todos os valores de
a
serão gerados, após
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]
- o modulo
e o incremento
forem relativamente primos,
for divisivel por todos os fatores primos de
,
for divisível por 4 se
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 ,
e
.
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_aleatoriolcg.anterior = 2222