Geradores congruentes lineares

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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]

  1. o modulo e o incremento forem relativamente primos,
  2. for divisivel por todos os fatores primos de ,
  3. 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

  1. Bolte, Joe. «Linear Congruential Generators». demonstrations.wolfram.com (em inglês). Consultado em 27 de janeiro de 2017 
  2. a b 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 
Wiki letter w.svg Este artigo é um esboço. Você pode ajudar a Wikipédia expandindo-o. Editor: considere marcar com um esboço mais específico.