Ir para o conteúdo

Geração de Números pseudo-aleatórios

Imaginem que querem fazer o vosso programa e querem ter uma função que gera números aleatórios ao vosso gosto.

Por exemplo, gerar valores pseudo-aleatórios com distribuição uniforme entre \(]0, 1]\) ou uma distribuição gaussiana de média nula e de variância unitária (ruído branco). Imaginem que não têm qualquer função que gerasse números aleatórios. Então este tópico tem a função de ensinar um algoritmo de um motor de números aleatórios e a sua manipulação.

A necessidade da semente de gerador de números aleatórios é fundamental em muitos casos como, por exemplo, para reproduzir eventos de jogo a posteriori (sistema de replay). Se garantirmos que o sistema de jogo é determinista (uma acção do jogador conduz sempre ao mesmo resultado), apenas precisamos de reintroduzir a semente do gerador de números aleatórios utilizado para as computações de AI, física, etc. e obtemos a mesma sequência de eventos. Sem falar, que facilita em muito o processo de debug.

A geração de ruído branco inicia-se com uma fórmula para produzir números aleatórios distribuídos uniformemente no intervalo \(]0, 1]\). Aplicando transformações convenientes na sequência distribuída uniformemente, podemos obter sequências de números aleatórios com distribuições e propriedades arbitrárias.

Um dos métodos preferidos para a geração de números aleatórios, designado por método congruencial, usa a seguinte fórmula recursiva:

\[ X(k) = [A * X(k - 1)]~modulo~M \]

com \(k = 1, 2, ...\)

Na fórmula, \(A\) é um inteiro entre \(1\) e \(M\), em que \(M\) é um número primo ou uma potência inteira de um número primo, \(p^m\). A geração de números aleatórios começa com a utilização da "semente" inicial \(X(0)\). A equação irá produzir inteiros uniformemente distribuídos entre \(1\) e \(M\). Dividindo \(X(k)\) por \(M\) podemos gerar valores do intervalo \(]0, 1[\) isto é, \(U(k) = X(k) = M\), onde \(U(k)\) é uma sequência uniformemente distribuída em \(]0, 1[\). Se \(M\) for muito grande e \(A\) for convenientemente escolhido, os números na sequência parecerão aleatórios (independentes) e a sequência terá um período máximo de \(M - 1\).

Para um gerador congruencial multiplicativo, se \(M\) for \(2^b\), onde \(b\) é o número de bits de um inteiro sem sinal (unsigned integer), o período máximo é \(M/4 = 2^b-2\). Isto pode ser obtido se a semente (\(X(0)\)) for um número ímpar e \(A\) obedeça à seguinte restrição:

\[ A = 8k +- 3 \]

(sendo \(k\) um número inteiro)

No caso de termos um gerador congruencial normal e a assumindo que o valor do módulo \(M\) é suficientemente grande — um bom exemplo seria \(2^b\), mas não é obrigatório — os valores de \(M\), \(A\) e de \(C\) obedecem aos seguintes critérios:

  • \(A > 0\); \(C > 0\).
  • \(C\) é primo relativo de \(M\) (o maior divisor comum de \(C\) e \(M\) é \(1\)).
  • Para todos os factores primos, \(p\), de \(M\), \(p\) necessita igualmente de ser factor de \(A-1\).
  • \(4\) precisa de ser um factor de \(A-1\) se \(4\) for um factor de \(M\).

Se \(M = 2^b\), podemos simplificar para as seguintes duas condições:

  • \(A = 4k + 1\), onde \(k\) é um inteiro positivo
  • \(C\) é ímpar

Seja agora \(X1\) e \(X2\), duas variáveis aleatórias independentes distribuídas uniformemente no intervalo \([0, 1]\). Então \(Y1\) e \(Y2\) definido por:

\[ Y1 = [ [-2 * ln(X1)] ] * 1/2 * cos(2 * pi * X2) \]
\[ Y2 = [ [-2 * ln(X2)] ] * 1/2 * cos(2 * pi * X1) \]

são variáveis aleatórias gaussianas, independentes, de média nula e variância unitária.

Este algoritmo, que permite obter um par de v.a. gaussianas a partir de um par de v.a. distribuídas uniformemente, é conhecido por método de Box-Muller. Note-se que as equações anteriores produzem números distribuídos no intervalo \(]-\infty; +\infty[\). Se m for o menor número real positivo que pode ser representado num dado computador, então o algoritmo produzirá números no intervalo \(]-a, a[\), com \(a = [-2 * ln(m)]^{1/2}\).