Geração de números pseudo-aleatórios (método congruencial e de Box-Muller)

[brink@ero]

Boas,

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 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, p^m. 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 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.

Seja agora X₁ e X₂, duas variáveis aleatórias independentes distribuídas uniformemente no intervalo [0; 1]. Então Y₁ e Y₂ definido por:

Y₁ = [-2 ln(X₁)]^1/2 cos(2 x pi x X₂)

Y₂ = [-2 ln(X₂)]^1/2 cos(2 x pi x X₁)

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; + inf[. 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.

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

Bibliografia: "Apontamentos de Sistemas de Controlo de Tráfego", Nunes Fernando Duarte, Dez. 2004, IST.

---

Espero que isto seja útil, principalmente em jogos  😉.

Cumpr. brink@ero

[UnKnowN]

Ya, Mt Bom, mas ha alguma linguagem que nao tenha Randomize ?

PS: É certo que se pode fazer 1 Randomize diferente usando esse método

[brink@ero]

Ya, Mt Bom, mas ha alguma linguagem que nao tenha Randomize ?

PS: É certo que se pode fazer 1 Randomize diferente usando esse método

O mais importante é o método de Box-Muller, que permite obter ruído branco. Isto é muito útil em muitas aplicações, principalmente em jogos/simuladores.

O outro método permite criar números pseudo-aleatórios, em que tu tens total controlo. E para que serve isto?

Bem, isto quer dizer que em dois computadores diferentes, com a mesma "semente" geras os mesmos números pseudo-aleatórios (nalgumas linguagens, acho que isto não é possível). Uma utilidade disto é uma coisa que pretendo fazer como part-time que é codificação pseudo-aleatória dos ficheiros, mas não vou usar este método.

Cumpr. brink@ero  ?

[UnKnowN]

Entendido 😉

[deathseeker25]

Gostava de ver o algoritmo implementado directamente no código para compreender melhor.

Já percebi qual a função base do algoritmo, no entanto queria ver que tipo de aplicação tem na programação... 😉

[pedrotuga]

Nao falta aí um traço de fracao na primeira eq?

uknown... existe alguma linguagem que nao tenha um randomize?

brinca, já vi que tu percebes disto da geração de numeros randómico.

epa... qual é a melhor forma de gerar um numero randómico entre a e b? como costumas fazer?

que parametros usam as funcoes que usas? tipo... as vezes a porra do compilador simplesmente pega no valor de um determinado endereço de memoria, o que é mau pois lá se vai a aleatoriedade.

Acho que há merdas que usam o relogio e coisas assim.

Uma ideia fixe seria usar a temperatura de algum dispositivo há alguma função em C/C++ que gere numero aleatorios baseando-se na temperatura do processador por exemplo?

[M6]

Excelente! 😉

Para o pessoal que pergunta se todas as linguagens não têm já um rnd: uma cena destas é muito mais do que um simples rnd.

Imaginem que querem fazer uma ferramenta de geração de dados aleatórios mantendo certas propriedades ou efectuando a geração acente em modelos matemáticos diferentes, este tipo de algoritmos é extremamente útil. Essa é a razão pela qual o Java, por exemplo, possui vários métodos de geração de valores aleatórios.

[UnKnowN]

Excelente! 😉

Para o pessoal que pergunta se todas as linguagens não têm já um rnd: uma cena destas é muito mais do que um simples rnd.

Imaginem que querem fazer uma ferramenta de geração de dados aleatórios mantendo certas propriedades ou efectuando a geração acente em modelos matemáticos diferentes, este tipo de algoritmos é extremamente útil. Essa é a razão pela qual o Java, por exemplo, possui vários métodos de geração de valores aleatórios.

PS: É certo que se pode fazer 1 Randomize diferente usando esse método

Eu percebi isso M6, mas de qq forma Obrigado 😉

[theproject]

Boas,

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 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, p^m. 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 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.

Seja agora X₁ e X₂, duas variáveis aleatórias independentes distribuídas uniformemente no intervalo [0; 1]. Então Y₁ e Y₂ definido por:

Y₁ = [-2ln(X₁)]^1/2cos(2 x pi x X₂)

Y₂ = [-2ln(X₂)]^1/2cos(2 x pi x X₁)

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; + inf[. 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.

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

Bibliografia: "Apontamentos de Sistemas de Controlo de Tráfego", Nunes Fernando Duarte, Dez. 2004, IST.

---

Espero que isto seja útil, principalmente em jogos  🙂 .

Cumpr. brink@ero  :smoke:

Boas, esqueceste-te de referir as condiçoes a que os parâmetros no método da congruencia devem obedecer entre si para se obter a maior sequência não repetida, eu não me lembro das condições, teria de ir ver ao meu caderno de Mat. discreta mas o que acontece é que se esses valores não obedecerem às condições a que me refiro a sequência gerada é muito pequena até se começar a repetir tipo

10 3 2 6 4 7 5 10 3 2 6 4 7 5 10 3 2 6 4 7 5 .... e portanto não é muito aleatória...

Nao falta aí um traço de fracao na primeira eq?

uknown... existe alguma linguagem que nao tenha um randomize?

brinca, já vi que tu percebes disto da geração de numeros randómico.

epa... qual é a melhor forma de gerar um numero randómico entre a e b? como costumas fazer?

que parametros usam as funcoes que usas? tipo... as vezes a porra do compilador simplesmente pega no valor de um determinado endereço de memoria, o que é mau pois lá se vai a aleatoriedade.

Acho que há merdas que usam o relogio e coisas assim.

Uma ideia fixe seria usar a temperatura de algum dispositivo há alguma função em C/C++ que gere numero aleatorios baseando-se na temperatura do processador por exemplo?

Todas as linguagens que conheco tem alguma funcao de geração de pseudo-aleatórios, mas como são pseudo-aleatórios, os numeros gerados dependem da semente (seed), o que normalmente se faz é ir buscar a semente por exemplo ao tempo do sistema no início do programa..

Gerar "verdadeiros" aleatórios requer normalmente hardware especial que usa fenómenos quanticos já naturalmente com alguma aleatoriedade e geram-se os números a partir daí, mas reparem que a aleatoriedade é muito difícil de definir, visto que para nós a aleatoriedade é nao conseguir a partir de uma sequência de números calcular a função que os gerou, mas mesmo nos fenómenos quanticos, se daqui a 100 anos se souber exactamente todos os fenómenos envolvidos por trás então também se pode prever o valor que vai ser dado pelo método de geração....

[]

[brink@ero]

Boas, esqueceste-te de referir as condiçoes a que os parâmetros no método da congruencia devem obedecer entre si para se obter a maior sequência não repetida, eu não me lembro das condições, teria de ir ver ao meu caderno de Mat. discreta mas o que acontece é que se esses valores não obedecerem às condições a que me refiro a sequência gerada é muito pequena até se começar a repetir tipo

10 3 2 6 4 7 5 10 3 2 6 4 7 5 10 3 2 6 4 7 5 .... e portanto não é muito aleatória...

É o seguinte, na bibliografia, não indica nenhuma fórmula para valores de A e de M de modo a que o periódo de repetição seja de máximo, ou seja, de M-1.

Mas dá uma sugestão, que numa fase de testes que eu fiz, foi o suficiente para obter a periodicidade máxima:

(...) em que M é um número primo ou uma potência inteira de um número primo, p^m.(...) 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.

---

Gerar "verdadeiros" aleatórios requer normalmente hardware especial que usa fenómenos quanticos já naturalmente com alguma aleatoriedade e geram-se os números a partir daí, mas reparem que a aleatoriedade é muito difícil de definir, visto que para nós a aleatoriedade é nao conseguir a partir de uma sequência de números calcular a função que os gerou, mas mesmo nos fenómenos quanticos, se daqui a 100 anos se souber exactamente todos os fenómenos envolvidos por trás então também se pode prever o valor que vai ser dado pelo método de geração....

Isso não é verdade, eu vivo nesse mundo. Não precisa estudar fenómenos quânticos para obter números aleatórios! Existe uma coisa chamada da Teoria dos caos e do efeito borboleta.

Por exemplo, conhece-se todas as equações responsáveis pelo movimento dos fluidos, mas este é influênciado com pequenas perturbações que são "impossíveis" de serem todas contabilizadas.

Por isso, retira-se toda a matemática pesada e exacta e estuda-se as probabilidades do seu movimento, por exemplo a meteorologia.

brinca, já vi que tu percebes disto da geração de numeros randómico.

epa... qual é a melhor forma de gerar um numero randómico entre a e b? como costumas fazer?

que parametros usam as funcoes que usas? tipo... as vezes a porra do compilador simplesmente pega no valor de um determinado endereço de memoria, o que é mau pois lá se vai a aleatoriedade.

Acho que há merdas que usam o relogio e coisas assim.

Em C/C++, existe as seguintes funções:

	srand(time(0));
return rand()%max;

Que usa o relógio como semente, e podes considerar como uma distribuição uniforme entre 0 e max-1. Para isso não precisas de aplicar o algoritmo congruente.

Uma ideia fixe seria usar a temperatura de algum dispositivo há alguma função em C/C++ que gere numero aleatorios baseando-se na temperatura do processador por exemplo?

Isso é uma má ideia, porque a temperatura varia continuamente (felizmente) e se nós quisermos uma amostrágem rápida de ruído este método torna-se inútil.

Mas se quiseres criar mesmo uma fonte de ruído, por exemplo de ruído branco, isso é muito fácil de arranjar.

Podes pegar num amplificador+sensor, por exemplo rádio, sintonizas no ruído e pronto, tens uma amostragem de ruído puro. 😛

Qualquer resistência em que passe corrente elêctrica e que esteja à um diferencial de potência é um emissor de ruído. Por isso basta um amplificador ou mesmo o próprio amplificador para tornar tal possível. Se eles quisessem era fácil de ter um pequeno dispositivo (com a tecnologia nano) como fonte de ruído puro. Mas isso é um acréscimo de € que não seria apreciado por todos, porque o ruído pseudo aleatório é suficiente.

---

Gostava de ver o algoritmo implementado directamente no código para compreender melhor.

Já percebi qual a função base do algoritmo, no entanto queria ver que tipo de aplicação tem na programação... 😛

Eu tambem gostava de partilhar, pelo menos a parte da codificação pseudo-aleatória. Eu considero que é a forma mais eficaz de codificação, sendo "impossível" alguem conseguir descodificar sem conhecer a semente. Os restantes métodos podem falhar na parte da regularidade, por exemplo um método simples de trocar as letras falha porque cada letra tem uma determinada frequência relativa num texto e com isso é possível descodificar, mesmo sem conhecer a chave de descodificação. Mas esta é a minha opinião.

Este sistema de codificação pseudo-aleatória é utilizado por exemplo para codificar o sinal do GPS.

Sobre os simuladores, eu normalmente uso o MatLab/Simulink para isso. Mas num laboratório de SCDTR (sistemas de controlo distribuídos em tempo real) tive de criar uma aplicação em C++ para controlar um sistema. Mas os testes duravam só uma hora e era necessário uma marcação. Assim, era necessário que na fase de testes o programa funciona-se perfeitamente.

Para isso criei um simulador do sistema para testar o programa em casa. Na altura desconhecia este algoritmo e com isso o simulador replicava um sistema perfeito sem ruído nos sensores.

Devido à isto, falhas no controlador não foram detectadas com o simulador.

Deixo aqui o link do Semi-Projecto

Cumpr. brink@ero  ?

[MiTh . Pt]

Olhem como e que se consegue aplicar a probabilidade com numeros aleatorios por exemplo no jogo omerta ( www.barafranca.com) em que eles nos dão uma probabilidade de conseguirmos por exemplo roubar um carro , roubar varias cenas , conforme a skill e outras variantes .

Mas a mim n interessam as variantes k essas n devem ser dificeis d implementar mas sim uma funçao k eu por exemplo dava a probabilidade de ser True ou False e essa funçao me devolvesse esse valor (ou True ou False ) em que podia por exemplo aplicar num jogo  tb , a probabilidade da fazer varias cenas .

E n tou a falar de atirar a moeda ao ar em k probabilidade e de 1/2.. mas sim eu dar a probabilidade e dpois lançar os dados (k neste caso seria um numero pseudo aleatório de preferencia entra ]0,1].

Uma coisa keu eu pensei , n sei se e possivel mas , tendo a funçao k gerasse o numero pseudo-aleatorio, se eu conseguise subtrair a percentagem de probabilidade (por exemplo 30% seriam 0,3) subtraia essa probabilidade de sair e se fosse um numero negativo retornava (é assim k se diz? ?) True , se fosse um Numero positivo retornava False. Neste caso teria de ver bem os intervalos pk o intervalo do numero aleatorio e de ]0,1] , se uma acçao tivesse 100 % d probabilidade de sair seria um numero entre ]-1,0] portanto o o intervalo alvo de um possivel True (desculpem a confusao se alguem n perceber digam.. 👍 ) seria  ]-n,0] em k n seria o valor de probabilidade.

Existe alguma maneira melhor? N consegui ver nada disso na net.. tb n procurei mt.. ?

[MiTh . Pt]

nota : eu tenho a impressao k este metodo n seria mt bom pois os numeros pekenos teriam sempre o valor de true e isso poderia afectar as probabilidades e assim quando usado mtas vezes , em numeros infinitamente grande de vezes ( vá eu sei k n preciso de um metodo assim tam aleatorio e com probabilidades tam bem calculadas quanto isso , mas para além de kerer usar isso num jogo na linguagem k ando a aprender (python , btw k mta da vossa ajuda ;)axo k n deve ser um metodo assim tam dificil d fazer )

kd comesei a ver essa cena de geração de numeros aleatorios (os verdadeiros) baseados em fenonemos quanticos ( ha outros não ditos aki como a diferença de "tempo" entre dois relogios ( k podem ser internos do computador) com "tic tacs" diferentes um a 100 por segundo outro a 100000, seila vi isso no wikipedia dpois meto o link se kiserem, tb ha outra maneira tem a ver com a utilizaçao de uma webcam e por exemplo se a taparem toda tem a ver com a analise da imagem preta ou n, e analisando a imagem com certas funçoes lixadonas decerto gerar um numero aletorio.

[fjeronimo]

Boas,

Olá a todos. Aproveito este meu primeiro post para falar deste assunto delicado com o qual lido diariamente, devido à sua importância na industria de jogos de computador onde trabalho.

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, p^m.

Na realidade, a fórmula fornecida é um caso especial do método congruencial: Trata-se de um gerador linear congruencial de pseudo números aleatórios multiplicativo. A fórmula base de um gerador linear congruencial normal[Wikimedia06] é:

X(k+1) = [A x X(k) + c] modulo M  números no intervalo [0, M-1]

Quando c=0, como no caso apresentado, estamos na presença de um gerador multiplicativo. São ligeiramente mais rápidos dado que não existe a adição na equação. No entanto, a sua utilização é mais complicada. Se qualquer número na sequência for zero, todos os seguintes serão zero igualmente. Dai a necessidade de limitar artificialmente o intervalo de geração para ]0, M-1]. Assim, um gerador multiplicativo não pode possuir um período máximo de M. Podemo-nos aproximar desse valor com uma escolha judiciosa do A e da semente X0 [Freeman04].

É o seguinte, na bibliografia, não indica nenhuma fórmula para valores de A e de M de modo a que o periódo de repetição seja de máximo, ou seja, de M-1.

Mas dá uma sugestão, que numa fase de testes que eu fiz, foi o suficiente para obter a periodicidade máxima:

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

Onde k é um inteiro qualquer.

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 [Freeman04]:

* 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 [Freeman04]:

* A = 4k + 1, onde k é um inteiro positivo

* C = ímpar

Ya, Mt Bom, mas ha alguma linguagem que nao tenha Randomize ?

PS: É certo que se pode fazer 1 Randomize diferente usando esse método

É verdade. Mas, infelizmente a maior parte das linguagens oferece implementações muito defeituosas de geradores de números aleatórios. Consideremos por exemplo o caso da função rand() do ANSI C. Esta função é notavelmente subespecificada, porque a função de geração não se encontra definida pelo standard. Na realidade, o standard ANSI C apenas afirma que a função rand() é um gerador de números aleatórios que gera inteiros no intervalo [0, RAND_MAX], com RAND_MAX definido no stdlib.h e sendo pelo menos 32767. Em abono da verdade, o standard inclui uma implementação. Mas trata-se apenas de um exemplo, oferecendo assim a possibilidade de criar um sem número de implementações desde que obedeçam aos dois critérios anteriores.

Com este grau de liberdade, as implementações iniciais das bibliotecas de C eram surpreendentemente más (algumas até iam ao ponto de utilizar o RANDU [Wikimedia06_2]). Hoje em dia, as coisas melhoraram mas a função rand() incluída nos actuais sistemas operativos da Microsoft  possui apenas 15 bits de estado (RAND_MAX = 32767) e repete-se após gerar 32768 valores. De notar que 32767 não é um grande número. Se RAND_MAX for apenas 32767, então provavelmente serão gerados 20,000 números aleatórios antes da sequência começar a perder a sua aleatoriedade (uma boa aproximação é que podem ser gerados 2/3 de RAND_MAX de números aleatórios antes de se detectar a falta de aleatoriedade) [Deley91]. Devido a estas limitações, o leitor é aconselhado a submeter a implementação de rand() do seu sistema a uma miríade de testes para garantir que se trata de um implementação aceitável.

Assim sendo, uma das grandes vantagens de usar um gerador de números pseudo aleatórios – a possibilidade de replicar uma sequência de números – encontra-se apenas marginalmente presente na função rand(). A função srand() é fornecida com o intuito de permitir a atribuição de sementes, mas não retorna obrigatoriamente o gerador ao estado desejado. A função mantém um estado interno de 32 bits, e o valor de retorno de 15 bits (nos casos onde RAND_MAX = 32767) é uma representação insuficiente do estado do gerador [Freeman04]. Isto significa que não possível reproduzir de forma segura a semente da função rand(), eliminando assim uma das vantagens dos geradores pseudo aleatórios [Dawson01].

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.

Em C/C++, existe as seguintes funções:

	srand(time(0));
return rand()%max;

Que usa o relógio como semente, e podes considerar como uma distribuição uniforme entre 0 e max-1. Para isso não precisas de aplicar o algoritmo congruente.

Esse exemplo apresenta alguns problemas de peso. Já abordei as limitações da função rand() e do srand(), por isso passo à frente. A utilização do módulo para limitar o número aleatório a um intervalo, apesar de intuitivo, é uma má ideia por um conjunto variado de motivos: distribuição não uniforme, dependências entre bits, o caso em que RAND_MAX+1 < max,  sobrevalorização dos bits mais baixos em detrimento dos mais altos. Este último ponto é particularmente relevante dado que para geradores lineares congruenciais, os bits mais baixos são muito menos aleatórios do que os mais altos. Aliás, pode-se dar o caso em que o bit mais baixo alterna entre 0 e 1, o que conduz a uma alternância de números pares e impares na geração (o leitor pode consultar [Hsieh06] para uma discussão aprofundada deste tópico).

Uma alternativa para adaptar um intervalo a outro consiste na seguinte fórmula:

NovoValor = NovoMinimo + (AntigoValor - AntigoMinimo) * (NovoMaximo - NovoMinimo) / (AntigoMaximo- AntigoMinimo)

Onde,

AntigoValor no intervalo [AntigoMinimo, AntigoMaximo]

NovoValor no intervalo [NovoMinimo, NovoMaximo]

Adaptando ao caso do número aleatório onde temos AntigoValor no intervalo [0, M-1] e NovoValor no intervalo [Min, Max] temos:

NovoValor = Min + Random * (Max – Min) / (Modulus -1)

No entanto, os problemas não acabam aqui (floats vs. integers, distribuição uniforme para inteiros, intervalos abertos vs. intervalos fechados,  etc.) mas este post já está suficientemente grande (estou a pensar escrever algo mais detalhado de futuro no entanto).

No final de contas, a utilização prende-se muito com as necessidades do projecto. No caso de um jogo, mais do que a aleatoriedade é a possibilidade de repetir a sequência gerada que interessa. Logo um gerador congruencial normal é normalmente mais do que suficiente (para os mais dedicados, podem utilizar o Mersenne Twister). Em contrapartida, estes nunca devem ser utilizados em simulações Monte Carlo ou em algoritmos criptográficos.

Se pretendermos geradores de números pseudo-aleatórios, as seguintes condições são normalmente desejadas:

* Reprodução – A partir da mesma semente, capacidade de reproduzir a mesma sequência de números.

* Eficiência – Os verdadeiros geradores de números aleatórios são lentos e ocupam MUITA memória. Os geradores de números pseudo-aleatórios são muito mais rápidos e guardam poucas variáveis em memória.

* Período longo – Os gerados de números pseudo-aleatorios repetem-se ao fim de X chamadas, que depende de gerador para gerador. Um bom gerador tem um período maior do que os números necessários.

* Aceitação estatística – Os números criados por um gerador de números aleatórios não são verdadeiramente aleatórios mas aparentam ser. Os testes estatísticos verificam a uniformidade e a independência dos valores. A uniformidade garante que cada valor tem uma probabilidade correcta. A independência garante que um valor não afecta a probabilidade de outro. Este último ponto é particularmente difícil de cumprir, visto que um valor de um gerador de números aleatórios é determinado a partir do anterior.

Por vezes a ilusão de aleatoriedade é mais importante do que a própria aleatoriedade. De tal modo, que se costuma utilizar algoritmos de filtragem para impedir que uma sequência de números aleatórios possua as seguintes características (para simplificar, assumo aqui uma sequência binária de 0s e 1s) [Rabin04]:

* Repetição longa do mesmo resultado, como por exemplo 11111111.

* Pouca alternância entre resultados, por exemplo 11110000.

* Repetição de padrões, como por exemplo 11001100 onde o padrão é 1100.

* Simetria de padrões, 11100111 onde o padrão é 1110.

Em conclusão, o leitor deve efectuar o maior número de testes possível do gerador de número aleatórios que escolher. Dois programas para realizar estes testes são o “ENT” [Walker98] e o “Diehard” [Marsaglia96] . O site “A collection of classical pseudorandom number generators with linear structures” [Entacher00] é igualmente muito interessante.

Espero que tenha sido útil. Desculpem o post tão longo.

Referências:

[Dawson01] Dawson, Bruce, “Game Input Recording and Playback”, Game Programming Gems 2, Charles River Media, 2001.

[Deley91] Deley, David W., “Computer Generated Random Numbers”, http://www.std.com/~franl/crypto/random-numbers.html, 1991.

[Entacher00] Entacher, Karl, “A collection of classical pseudorandom number generators with linear structures”, http://crypto.mat.sbg.ac.at/results/karl/server/, 2000.

[Freeman04] Freeman-Hargis, James, “The Statistics of Random Numbers”, AI Game Programming Wisdom 2, Charles River Media, 2004.

[Hsieh06] Hsieh, Paul, “Misconceptions about rand()”, 2006.

[Marsaglia96] Marsaglia, George, “Diehard: A Battery of Tests for Random Number Generators”, http://www.stat.fsu.edu/pub/diehard/, 1996.

[Rabin04] Rabin, Steve, “Filtered Randomness for AI Decisions and Game Logic”, AI Game Programming Wisdom 2, Charles River Media, 2004.

[Walker98] Walker, John, “ENT: A Pseudorandom Number Sequence Test Program”, http://www.fourmilab.ch/random/, 1998.

[Wikimedia06] Wikimedia, Foundation, “Linear Congruential Generator”, http://en.wikipedia.org/wiki/Linear_congruential_generator, 2006.

[Wikimedia06_2] Wikimedia, Foundation, “RANDU”, http://en.wikipedia.org/wiki/RANDU, 2006.

[NuGuN]

Muito porreiro, já me tinha perguntado como o sistema gerava números aleatórios, agora já tenho uma ideia  😉

Cumps

[brink@ero]

Bem-vindo ao fórum fjeronimo

Obrigado por completares o tutorial  😄

Cumpr. bk@ero  😉

[fjeronimo]

Em 05/11/2006 às 20:06, brink@ero disse:

Bem-vindo ao fórum fjeronimo

Obrigado por completares o tutorial  😄

Cumpr. bk@ero  👍

Obrigado. Descobri o fórum a partir do site da Gamedev-PT (http://www.gamedev-pt.net). Parabéns pela iniciativa. Espero poder participar mais de futuro.

[NuGuN]

Pessoal, estive a tentar passar esses exemplo para código mas não sou capaz  ?  Alguem me pode dar um exemplo em código (não interessa a linguagem)

Cumps

[brink@ero]

Pessoal, estive a tentar passar esses exemplo para código mas não sou capaz  ?  Alguem me pode dar um exemplo em código (não interessa a linguagem)

Cumps

Por acaso fiz um pequeno código em C/C++ com este algoritmo para encriptar ficheiros .txt (muito básico e baixa interface com o utilizador)

Se tiveres pressa->pm

Cumpr. bk@ero  👍

[NuGuN]

Gostava de ver isso so fosse possível  🙂

Não, não tenho pressa  👍

Cumps