Ferramentas de Utilizador

Ferramentas de Site


algoritmo:aleatorio

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 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 (X0) for um número ímpar e A obedeça à seguinte restrição Freeman04:

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 = [[-2ln(X1)]]1/2cos(2 * pi * X2) Y2 = [[-2ln(X2)]]1/2cos(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).

X módulo Y, é o resto da divisão entre X e Y!
algoritmo/aleatorio.txt · Esta página foi modificada pela última vez em: 2018/05/14 21:37 (Edição externa)