Ferramentas de Site


algoritmo:aleatorio

Esta é uma versão antiga do documento!


FIXME Passar as expressões matematicas para mathML e escapar alguns caracteres.

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

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

Por exemplo fazer uma geração de 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 gera-se números aleatórios. Então este tópico tem a função de ensinar um algoritmo dum motor de n.º aleatórios e sua manipulação.

A necessidade de 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 X(k - 1)]] modulo M;  k = 1, 2, ...

onde A é um inteiro entre 1 e M, em que M é um número primo ou uma potência inteira de um número primo, pm. A geração de números aleatórios começa com a utilização da "semente" inicial X(0). A equação 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 em0; 1Se 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 unsigned integer, o período máximo é M/4 = 2^b-2. Isto pode ser obtido se a semente (X0) for um número impar e A obedeça à seguinte restrição [[Freeman04:

A = 8k +- 3

(sendo k um número inteiro)

No caso de termos um gerador congruential 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 simplicar 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 1. Então Y1 e Y2 definido por:

Y1 = [[-2ln(X1)]]1/2cos(2 x pi x X2)
 Y2 = [[-2ln(X2)]]1/2cos(2 x pi x 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 ]] - inf; + infSe 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; acom a = [[-2 ln(m)1/2.

Nota: X módulo Y, é o resto da divisão entre X e Y!

algoritmo/aleatorio.1190938174.txt.gz · Última modificação em: 2018/05/14 21:37 (edição externa)