Curso de C
Números Aleatórios
Você está em: MarMSX >> Cursos >> C
Um gerador de números aleatórios é um dispositivo no qual gera uma seqüência de números ou símbolos que não podem ser previstos ou determinados, mas são obtidos ao acaso.
No nosso cotidiano encontramos formas para a geração de dados aleatórios como o lançamento de um dado, uma moeda e quando embaralhamos as cartas de um baralho.
Os números aleatórios são utilizados em diversas aplicações computacionais como simulações e jogos.
Entretanto o termo "número aleatório" é algo absurdo. Por exemplo, o número 7 é aleatório? e 10? Obviamente que não.
O objetivo de um gerador de números aleatórios é criar uma seqüência numérica que parace estar em uma ordem aleatória. Mas, afinal, o que vem a ser uma seqüência aleatória de números?
Para compreender melhor esse conceito, vejamos o exemplo a seguir.
Seja a seguinte seqüência numérica:
1 2 3 4 5 6 7 8 9 0
Se ela fosse criada através da digitação do teclado do computador, ela com certeza não seria considerada como aleatória. Entretanto, se essa seqüência fosse obtida através do sorteio de bolinhas dentro de um saco contendo essas numerações? Nesse caso, seria considerado como uma seqüência aleatória.
Dessa forma, a questão da aleatoriedade está relacionada com a forma de como os números foram gerados e não com a seqüencia em si.
Os números aleatórios gerados por computadores são determinísticos, uma vez que cada número depende do número anterior, exceto o primeiro. Tecnicamente, isto significa que uma seqüência quase aleatória pode ser gerada pelo computador. Além disso, é desejável que os números dessa seqüência sejam uniformemente distribuídos, isto é, cada número tenha a mesma probabilidade de sair.
Texto adaptado de [1] e [2].
Geradores de números pseudo-aleatórios (PRNG)
Esse método utiliza algoritmos que produzem longas seqüências de resultados aparentemente aleatórios, no qual são determinados por um valor inicial chamado de semente. Através de uma fórmula recorrente, ou seja, que depende do número aleatório anterior, um novo valor é calculado. Assim, quando conhecemos o valor da semente, podemos reproduzir toda aquela seqüência de números aleatórios [adaptado 1].
Os números aleatórios podem ser gerados através da seguinte equação [2]:
Rn+1 = (aRn+c) mod m
Onde:
- R >= 0
- a >= 0
- c >= 0
- m > R, a e c
Esse método é chamado de método da congruência linear.
A eficiência desse método está ligada a escolha dos valores de a, c e m.
O valor do módulo m é o intervalo dos números aleatórios. Por exemplo, se m=3, os seguintes números poderão ser gerados: 0, 1 e 2. A escolha de m não interfere na aleatoriedade dos números.
Os valores escolhidos para multiplicador a e o incremento c dependem de alguns testes para confirmar se são adequados.
O exemplo a seguir [2] mostra um gerador de números aleatórios simples.
#include <stdio.h>
long int r=100001;
float rand1()
{
long int a=125, m=2796203;
r = (r*a) % m;
return (float) r/m;
}
main()
{
int i;
for (i=0; i<5; i++)
printf("Número %d: %.2f\n", i+1, rand1());
}
Saída:
Número 1: 0.47
Número 2: 0.80
Número 3: 0.88
Número 4: 0.41
Número 5: 0.96
Vamos analisar alguns aspectos desse gerador.
Podemos observar que há um primeiro valor de R, declarado na linha:
long int r=100001;
Esse primeiro valor de R é chamado de semente, por ser um valor inicial necessário para a execução da função.
O número aleatório calculado deverá ser do tipo inteiro, para manter a congruencidade linear [2]. Entretanto, algumas linguagens como o Basic e o C retornam números aleatórios entre 0 e 1. Esse é o motivo da divisão de r/m no retorno do valor. Se omitirmos a razão r/m, o valor retornado é um inteiro entre 0 e m.
Conforme dito anteriormente, a partir de um determinado valor de semente, teremos sempre a mesma seqüência de números aleatórios. Rode o programa várias vezes e comprove.
No programa anterior, a função randômica não é capaz de alterar o valor da semente criada para ela. No programa a seguir [2], vamos permitir que o usuário determine o valor da semente.
#include <stdio.h>
long int r;
int flag_seed=0;
float rand2(int seed)
{
long int a=125, m=2796203;
if (!flag_seed)
{
r = seed*1000;
flag_seed=1;
}
r = (r*a) % m;
return (float) r/m;
}
main()
{
int i;
for (i=0; i<5; i++)
printf("Número %d: %.2f\n", i+1, rand2(10));
}
Saída:
Número 1: 0.45
Número 2: 0.88
Número 3: 0.92
Número 4: 0.81
Número 5: 0.20
Mudando o valor da semente para 123 na linha:
printf("Número %d: %.2f\n", i+1, rand2(123));
Saída:
Número 1: 0.50
Número 2: 0.32
Número 3: 0.50
Número 4: 0.16
Número 5: 0.79
Geradores de números aleatórios via hardware (HRNG)
Esse método se baseia na medição de alguns fenômenos físicos que se espera ser aleatórios. Alguns exemplos são o ruído atmosférico, termal ou qualquer outro fenômeno eletromagnético [2]. Em termos de computação, podemos medir o valor atual do relógio do sistema.
Nos exemplos anteriores, vimos que conseguimos gerar uma seqüência de números pseudo-aleatórios. Entretanto, esbarramos em um problema essencial: a seqüência é a mesma para uma determinada semente. Para solucionar esse problema, iremos introduzir uma informação aleatória de "verdade": o valor do relógio do sistema como semente.
Para gerar um verdadeiro número aleatório, o Expert utiliza seu relógio interno que mede a passagem de tempo em microssegundos [3]. O valor desse tempo é um parâmetro aleatório e pode ser utilizado através da função TIME [3].
No caso da linguagem Basic do MSX, a função RND(X) irá gerar um número aleatório da seguinte maneira:
- Se X=0, repete último número aleatório gerado.
- Se X>0, gera uma seqüência aleatória baseada em uma semente do sistema.
- Se x<0, gera um número aleatório com base no valor de X.
Exemplo:
10 PRINT RND(1)
20 PRINT RND(1)
30 PRINT RND(-1)
40 PRINT RND(-1)
50 PRINT RND(-4)
60 PRINT RND(0)
Saída:
.59521943994623
.10658628050158
.04389820420821
.04389820420821
.74389820420821
.74389820420821
Observe que para qualquer valor positivo, a seqüência das duas primeiras linhas será sempre a mesma. Ao dar o comando RUN, a semente é reinicializada.
Ao utilizarmos o "-TIME" como o parâmetro de RND, a semente é utilizada e é gerada com base no valor atual do relógio do MSX.
No C padrão do PC e MSX, a função rand() da biblioteca stdlib.h retorna um número inteiro entre 0 e RAND_MAX. No caso do MSX, RAND_MAX vale 32.767 e no PC 2.147.483.647.
O programa a seguir irá retornar dois números aleatórios entre 0 e 9.
#include <stdio.h>
#include <stdlib.h>
main()
{
printf("Valor aleatório entre 0 e 9: %d\n", rand() % 10);
printf("Valor aleatório entre 0 e 9: %d\n", rand() % 10);
}
Saída:
Valor aleatório entre 0 e 9: 3
Valor aleatório entre 0 e 9: 6
Rode o programa várias vezes e a seqüência será a mesma. Isso acontece porque o programa anterior utiliza a função rand() que é inicializada com uma semente padrão.
Podemos utilizar a função srand(semente) para determinar o valor da semente.
#include <stdio.h>
#include <stdlib.h>
main()
{
srand(10);
printf("Valor aleatório entre 0 e 9: %d\n", rand() % 10);
printf("Valor aleatório entre 0 e 9: %d\n", rand() % 10);
}
Saída:
Valor aleatório entre 0 e 9: 5
Valor aleatório entre 0 e 9: 8
Os valores são diferentes, mas ao rodarmos o programa várias vezes, iremos constatar que a seqüência será a mesma para essa semente.
Para obtermos uma seqüência realmente aleatória, vamos passar como parâmetro para srand() o valor do relógio do sistema.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
main()
{
srand(time(NULL));
printf("Valor aleatório entre 0 e 9: %d\n", rand() % 10);
printf("Valor aleatório entre 0 e 9: %d\n", rand() % 10);
}
Saída:
Valor aleatório entre 0 e 9: 6
Valor aleatório entre 0 e 9: 7
Tente rodar mais duas vezes agora. Veja as saídas que eu obtive:
1a. vez:
Valor aleatório entre 0 e 9: 2
Valor aleatório entre 0 e 9: 7
2a. vez:
Valor aleatório entre 0 e 9: 8
Valor aleatório entre 0 e 9: 4
O uso correto de srand()
Veja o programa a seguir:
#include <stdio.h>
#include <stdlib.h>
main()
{
int i;
srand(1234);
for (i=0; i<5; i++)
printf("Valor aleatório entre 0 e 9: %d\n", rand() % 10);
}
Saída:
Valor aleatório entre 0 e 9: 4
Valor aleatório entre 0 e 9: 9
Valor aleatório entre 0 e 9: 5
Valor aleatório entre 0 e 9: 7
Valor aleatório entre 0 e 9: 0
E se passarmos srand() para dentro do laço for, ou seja, sempre alterar a semente antes de chamar rand()?
#include <stdio.h>
#include <stdlib.h>
main()
{
int i;
for (i=0; i<5; i++)
{
srand(1234);
printf("Valor aleatório entre 0 e 9: %d\n", rand() % 10);
}
}
Saída:
Valor aleatório entre 0 e 9: 1
Valor aleatório entre 0 e 9: 1
Valor aleatório entre 0 e 9: 1
Valor aleatório entre 0 e 9: 1
Valor aleatório entre 0 e 9: 1
Uma vez a semente está sempre sendo alterada para o mesmo valor, obteremos os mesmos números.
E se nesse último exemplo substituirmos srand(1234) por srand(time(NULL))? Dependendo da velocidade de processamento do computador, iremos obter também a seqüência dos mesmos números. Testes no PC e no MSX confirmaram isso. Mas nesse caso, como a semente é aleatória, poderíamos ter uma seqüência de 0's, 1's, 2's etc.
O ideal é inicializar a semente com o valor do relógio do sistema e uma única vez.
Nota importante: quando se deseja repetir a mesma seqüência de números aleatórios obtidos em uma experiência qualquer, utilizamos uma determinado valor de semente em vez do relógio do sistema. Assim, podemos repetir a experiência e obter sempre os mesmos resultados.
Referências:
[1]- Random number generation. Em Wikipedia, http://en.wikipedia.org/wiki/Random_number_generation
[2]- C Avançado - Guia do usuário. Herbert Schildt, Ed. McGraw-Hill, 1987.
[3]- Dominando o Expert. Pierluigi Piazzi, editora Aleph, 1987.