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.

Mapa de retorno tridimensional para RANDU

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

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

o modulo $m$ e o incremento $c$ forem relativamente primos,
$a-1$ for divisivel por todos os fatores primos de $m$ ,
$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.^[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 $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

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

Este artigo é um esboço. Você pode ajudar a Wikipédia expandindo-o.

Editor: considere marcar com um esboço mais específico.

[1] Bolte, Joe. «Linear Congruential Generators». demonstrations.wolfram.com (em inglês). Consultado em 27 de janeiro de 2017

[:0-2] Knuth, Donald E. Art of Computer Programming, Volume 2: Seminumerical Algorithms. [S.l.]: Addison-Wesley Professional. ISBN 978-0-321-63576-1

[3] Hull, T. E.; Dobell, A. R. (1 de janeiro de 1962). «Random Number Generators» (PDF). SIAM Review. 4 (3): 230-254

[4] Severance, Frank (2001). System Modeling and Simulation. [S.l.]: John Wiley & Sons, Ltd. 86 páginas. ISBN 0-471-49694-4

[1]

[2]

[3]

[4]