Geradores congruentes lineares
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Randu2.png/220px-Randu2.png)
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:
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
[editar | editar código-fonte]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
[editar | editar código-fonte]Python
[editar | editar código-fonte]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
Notas e Referências
- ↑ Bolte, Joe. «Linear Congruential Generators». demonstrations.wolfram.com (em inglês). Consultado em 27 de janeiro de 2017
- ↑ a b Knuth, Donald E. Art of Computer Programming, Volume 2: Seminumerical Algorithms. [S.l.]: Addison-Wesley Professional. ISBN 978-0-321-63576-1
- ↑ Hull, T. E.; Dobell, A. R. (1 de janeiro de 1962). «Random Number Generators» (PDF). SIAM Review. 4 (3): 230-254
- ↑ Severance, Frank (2001). System Modeling and Simulation. [S.l.]: John Wiley & Sons, Ltd. 86 páginas. ISBN 0-471-49694-4