Números Aleatórios

O uso de números aleatórios na programação é um assunto fascinante. Eles são usados, por exemplo, em simulações, jogos e criptografia. Entretanto, a geração e o uso de números aleatórios não é uma questão trivial. É comum vermos programadores novatos confusos com o assunto e não é raro ocorrer de um programador experiente cometer um erro.

O Que É Um Número Aleatório?

Esta é uma questão que pode parecer trivial, mas a resposta pode ser complexa e filosófica. Como Knuth diz no volume 2 de "The Art of Computer Programming", não é exato falar em "números aleatórios" (2 é um número aleatório? E o 3?). O que queremos é uma sequência de números na qual cada número tem uma certa probabilidade de ocorrer, independente do número anterior.

Esta duas afirmações podem parecer contraditórias. Consideremos o caso mais comum, em que se deseja que todos os números possíveis tenham a mesma probabilidade (ou seja, uma distribuição uniforme). Consideremos ainda que estamos gerando dígitos de 0 a 9. Se acabamos de obter um 0, a nossa intuição (errada) é que é menos provável obter um outro zero em seguida. Na verdade, ao examinar uma sequência grande de números realmente aleatórios com distribuição uniforme, veremos que na média a probabilidade de ocorrer cada número é igual e independe do número anterior e que o mesmo ocorre com as subsequências de "n" números. Continuando o nosso exemplo dos dígitos, se observarmos um bilhão de dígitos veremos que o 0 terá em média a probabilidade de 1/10 e a sequência 00 a probabilidade de 1/100 (assim como todas as outras sequências de 2 dígitos).

Para conferir se uma sequência é realmente aleatória podem ser aplicados uma série de testes estatísticos. O livro do Knuth apresenta estes testes assim como definições mais formais.

Como Gerar Números Aleatórios no Computador?

Os computadores tipicamente não tem recursos para gerar por hardware números realmente aleatórios (ou próximos disto). Uma possibilidade é o uso de uma tabela gerada previamente, mas este método é claramente limitado.

A solução (que foi proposta por von Neumann em 1946) é utilizar um algorítimo que a partir do número atual determina o próximo número da sequência. É o que chamamos de sequência pseudo-aleatória.

Criar um algorítimo adequado não é simples. Este é um bom ponto para introduzir a rotina clássica do xkcd:

Ok, esta rotina não gera uma distribuição uniforme. Que tal o meu aperfeiçoamento abaixo?

int aleat (void)
{
static num = 1;

num = (num + 1);
if (num > 6)
  num = 1;
return num;
}

Embora os números de 1 a 6 tenham a mesma probabilidade de sair, o número gerado é totalmente dependente do anterior e somente algumas sequências de dois números são possíveis.

Mesmo assim, isto não é muito diferente do método mais usual, chamado de Congruência Linear:

X_n+1 = (aX_n + c) mod m

Em outras palavras, o número seguinte é obtido multiplicando o número atual por uma constante a, somando ao resultado uma constante c e pegando o resto da divisão por uma terceira constante (m).

Os números a, c e m são inteiros escolhidos com cuidado (novamente, ver no livro do Knuth). Este algorítimo gera números inteiros de 0 a m-1. Em um certo ponto esta sequência passará a se repetir. Uma escolha adequada de a, c e m garante uma sequência longa (idealmente de comprimento m).

O segredo para não incorrer no problema da minha versão é usar um m alto e usar a operação de módulo (resto) para obter um número na faixa desejada. Por exemplo, se tivermos uma função rnd() que retorna um número aleatório entre 0 e 1000000, 1+(rnd() mod 6) simula de forma satisfatória o rolar de um dado.

Pegando um exemplo mais concreto, a rotina rand() do Microsoft C 2005 usa a congruência linear com a = 214013, c = 2531011 e m = 0xFFFFFFFF. O número retornado são os 16 bits mais significativos do número gerado, módulo 0x7FFF (ficando desta forma na faixa 0 a 32767). A rotina srand() determina o número inicial (a chamada semente).

Usando a Rotina rand()

A rotina rand() do C (ou o seu equivalente em outras linguagens) é muito fácil de usar (mas não é necessariamente fácil usá-la de modo correto).

Se for usada sempre a mesma semente, a mesma sequência sera gerada. Isto pode ser útil na fase de testes de um programa. Para alterar a semente, usa-se a rotina srand(). Uma maneira típica de usar isto é iniciá-la com a hora atual (como o retorne de time()).

Em aplicações críticas (como criptografia) é preciso tomar o cuidado para que a semente seja razoavelmente aleatória. Se, por exemplo, você usar o número de minutos desde que a máquina for ligada e o seu software é executado automaticamente quando a máquina é ligada, a semente tenderá a variar pouco.

Como dito, rand() retorna um número inteiro de 0 a 32767. Para gerar um número inteiro entre dois números a e b (inclusive), podemos usar a fórmula

a + (rnd() % (b-a+1)

Isto vai dar bons resultados desde que (b-a) seja bem menor que 32767. Se, por exemplo, tentarmos gerar números de 0 a 30000, vamos observar que os números de 0 a 2767 serão mais frequentes.


Uma necessidade frequente é colocar em ordem aleatória uma lista de itens (por exemplo, embaralhar um conjunto de cartas). No próximo post vamos ver como a Microsoft se confundiu ao fazer isto e como fazê-lo corretamente.