Geradores congruentes lineares

Mapa de retorno tridimensional para RANDU

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:

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

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

A semente são inteiros constantes que definem o gerador. Se c = 0 {\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 c ≠ 0 {\displaystyle 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 {\displaystyle m} e dependo da escolha do fator a {\displaystyle a} pode ser ainda menor que o modulo. Quando um gerador possui um período completo, todos os valores de 0 {\displaystyle 0} a m − 1 {\displaystyle m-1} serão gerados, após m {\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 m {\displaystyle m} e o incremento c {\displaystyle c} forem relativamente primos,
  2. a − 1 {\displaystyle a-1} for divisivel por todos os fatores primos de m {\displaystyle m} ,
  3. a − 1 {\displaystyle a-1} for divisível por 4 se m {\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 c {\displaystyle c} , m {\displaystyle m} e a {\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.

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

  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 
Este artigo é um esboço. Você pode ajudar a Wikipédia expandindo-o. Editor: considere marcar com um esboço mais específico.
  • Portal da matemática