$\definecolor{highlight}{RGB}{2, 154, 207}$$\definecolor{extralight}{RGB}{217, 35, 15}$

Hoje estudaremos o método que foi criado por Derrick Henry "Dick" Lehmer em 1951 (65 anos atrás) para a geração de números pseudoaleatórios.


Ele é considerado um dos algoritmos mais antigos e o mais conhecido para este propósito e possui em sua forma original a seguinte representação matemática:


$X_{n+1} = (aX_{n} + c) \bmod m$


Valores para cada variável do algoritimo
Cada variável possui um conjunto de regras para serem válidas dentro da equação:


$\color{highlight}m$ | Modulus (Módulo)
$\color{gray}X_{n+1} = (aX_{n} + c) \bmod \color{highlight}m$

Número inteiro maior que zero:
$\color{highlight}m\color{gray} = ℤ > 0$

$\color{highlight}a$ | Multiplier (Multiplicador)
$\color{gray}X_{n+1} = (\color{highlight}a\color{gray}X_{n} + c) \bmod m$

Número inteiro maior que zero e menor que $\color{highlight}m$:
$\color{highlight}a\color{gray} = ℤ > 0 < m$

$\color{highlight}c$ | Increment (Incremento)
$\color{gray}X_{n+1} = (aX_{n} + \color{highlight}c\color{gray}) \bmod m$

Número inteiro maior ou igual a zero e menor que $\color{highlight}m$:
$\color{highlight}c\color{gray} = ℤ \ge 0 < m$

$\color{highlight}X_{0}$ | Seed Number (Semente Aleatória)
$\color{gray}X_{n+1}\color{gray} = (a\color{highlight}X_{0}\color{gray} + c) \bmod m$

Número inteiro maior ou igual a zero e menor que $\color{highlight}m$:
$\color{highlight}X_{0}\color{gray} = ℤ \ge 0 < m$

Resolvendo a Equação


Para poder escrever o algorítimo precisamos entender como resolver a equação. Daremos os seguintes valores para as variáveis:

$\color{highlight}m$ (modulus) $\color{gray}=$ $5$
$\color{highlight}a$ (multiplier) $\color{gray}=$ $2$
$\color{highlight}c$ (increment) $\color{gray}=$ $3$
$\color{extralight}X_{0}$ (seed) $\color{gray}=$ $0$

Com estes valores iniciais para cada variável, vamos resolver a equação:


1 |

Já temos o nosso valor inicial para $\color{extralight}X_{0}$, então vamos descobrir o valor do próximo $X$, o $\color{highlight}X_{1}$:

$\color{gray}X_{1} = (\color{highlight}a\color{extralight}X_{0}\color{gray} + \color{highlight}c\color{gray}) \bmod \color{highlight}m$

2 |

Substituímos as variáveis por seus valores: $\color{highlight}a\color{gray} = 2$, $\color{extralight}X_0\color{gray} = 0$, $\color{highlight}c\color{gray} = 3$ e $\color{highlight}m\color{gray} = 5$.

$\color{gray}X_{1} = ((\color{highlight}2\color{gray} \times \color{extralight}0\color{gray}) + \color{highlight}3\color{gray}) \bmod \color{highlight}5$

3 |

Resolvemos primeiro o que está dentro dos parênteses: $\color{gray}2 \times 0 = 0$, então $\color{gray}0 + 3 = \color{highlight}3$.

$\color{gray}X_{1} = \color{highlight}3\color{gray} \bmod \color{highlight}5$

4 |

O operador $\bmod$ é o resto da divisão inteira. Fazemos $3 \div 5 = 0$, então $5 \times 0 = 0$ e do $0$ para chegar no $3$ faltam $\color{extralight}3$:

$\color{gray}X_{1} = \color{extralight}3$

5 |

Pronto, o nosso primeiro número pseudoaleatório gerado é $\color{extralight}3$! Resumindo, fizemos:

$\color{gray}X_{1} = (\color{highlight}a\color{extralight}X_{0}\color{gray} + \color{highlight}c\color{gray}) \bmod \color{highlight}m$
$\color{gray}X_{1} = ((\color{highlight}2\color{gray} \times \color{extralight}0\color{gray}) + \color{highlight}3\color{gray}) \bmod \color{highlight}5$
$\color{gray}X_{1} = \color{highlight}3\color{gray} \bmod \color{highlight}5$
$\color{gray}X_{1} = \color{extralight}3$

6 |

Para calcular o nosso próximo número pseudoaleatório, basta encontrar o valor do próximo $X$, o $\color{highlight}X_2$ resolvendo a mesma equação, mas dessa vez utilizando o valor de $X_1$ como base:

$\color{gray}X_{2} = (\color{highlight}a\color{extralight}X_{1}\color{gray} + \color{highlight}c\color{gray}) \bmod \color{highlight}m$
$\color{gray}X_{2} = ((\color{highlight}2\color{gray} \times \color{extralight}3\color{gray}) + \color{highlight}3\color{gray}) \bmod \color{highlight}5$
$\color{gray}X_{2} = \color{highlight}9\color{gray} \bmod \color{highlight}5$
$\color{gray}X_{2} = \color{extralight}4$

7 |

Para calcular $\color{highlight}X_3$, fazemos:

$\color{gray}X_{3} = (\color{highlight}a\color{extralight}X_{2}\color{gray} + \color{highlight}c\color{gray}) \bmod \color{highlight}m$
$\color{gray}X_{3} = ((\color{highlight}2\color{gray} \times \color{extralight}4\color{gray}) + \color{highlight}3\color{gray}) \bmod \color{highlight}5$
$\color{gray}X_{3} = \color{highlight}11\color{gray} \bmod \color{highlight}5$
$\color{gray}X_{3} = \color{extralight}1$

8 |

E podemos calcular o $\color{highlight}X_4$ também, e assim por diante:

$\color{gray}X_{4} = (\color{highlight}a\color{extralight}X_{3}\color{gray} + \color{highlight}c\color{gray}) \bmod \color{highlight}m$
$\color{gray}X_{4} = ((\color{highlight}2\color{gray} \times \color{extralight}1\color{gray}) + \color{highlight}3\color{gray}) \bmod \color{highlight}5$
$\color{gray}X_{4} = \color{highlight}5\color{gray} \bmod \color{highlight}5$
$\color{gray}X_{4} = \color{extralight}0$


0 Semente
$\color{gray}(\color{highlight}a\color{extralight}X_{n}\color{gray} + \color{highlight}c\color{gray}) \bmod \color{highlight}m$ Equação LCG
- Resultado de $X_{1}$

Calculando até $\color{highlight}X_4$ conseguimos os seguintes números pseudoaleatórios: [3, 4, 1, 0]. Pronto! Este é o processo para gerar números pseudoaleatórios pelo algoritimo LCG.