quarta-feira, 26 de setembro de 2007

Como gerar números aleatórios

Como eu disse no post anterior, não existem números aleatórios em computação. Mas existem maneiras de conseguir números pseudoaleatórios com uma randomicidade (viva o neologismo) satisfatória.

Existem dois jeitos de se conseguir números aleatórios.

a) Monitoramento de ambiente: O programa monitora algum evento externo, como temperatura, umidade do ar, velocidade do vento, etc, e utiliza essa variável como base para uma função de geração de números;
b) Pseudoaleatoriedade: Projetar uma fórmula que satisfaça 3 condições essenciais:

  1. Não repetição: A fórmula não deve formar ciclos, nem produzir números repetidos propositalmente.
  2. Distribuição numérica razoável: A fórmula deve produzir uma boa faixa numérica, não se restringindo a poucos números.
  3. Imprevisibilidade: A fórmula deve ser produzida de modo que o próximo número gerado não possa ser previsto sem o prévio conhecimento da fórmula.
O Java, ou mais precisamente a classe java.util.Random usa a opção "b", mas utiliza como seed (o número inicial que gerará todos os outros) a variável mais simples a qual ele tem acesso. A máquina virtual do java captura a quantidade de milissegundos entre 01/01/1970 e o momento exato em que a função foi chamada e aplica a seguinte fórmula:


numeroinicial = (numeroinicial ^ 0x5DEECE66DL) & ((1L << 48) - 1);


A partir desta fórmula, os números randômicos serão obtidos da seguinte maneira:


synchronized protected int next(int bits) {
numeroinicial = (numeroinicial * 0x5DEECE66DL + 0xBL) & ((1L <<>>> (48 - bits));
}


Já o C usa a seguinte fórmula:


int rand()
{
random_seed = random_seed * 1103515245 +12345;
return (unsigned int)(random_seed / 65536) % 32768;
}


Legal né?

Links:
How stuff works
Random number generators

Té mais o/

Um comentário:

Anônimo disse...

Ma nigga, não tem como separar teu feed do blog com o do delicious?