Números pseudo-aleatórios

Por vezes necessitamos de simular acontecimentos aleatórios no computador:

simular o lançamento de um dado;
baralhar uma pilha de cartas;
escolher coordenadas gráficas para um objeto num jogo;
mais genericamente: simular eventos imprevistos.

Podemos fazer tudo isto usando geradores de números pseudo-aleatórios.

Pseudo-aleatórios em C

#include <stdlib.h>

int rand(void);

Cada chamada gera um novo pseudo-aleatório
Valores inteiros no intervalo 0 a RAND_MAX inclusivé
RAND_MAX está definido em stdlib.h
- o valor depende da implementação
- garantidamente maior ou igual a 32767
Não podemos modificar RAND_MAX (é uma constante)

Exemplo

Gerar e imprimir uma amostra de pseudo-aleatórios.

#include <stdlib.h>
#include <stdio.h>

int main(void) {
   int i;
   printf("RAND_MAX=%d\n", RAND_MAX);
   for (i = 0; i<10; i++)
      printf("%d\n", rand());
   return 0;
}

Execução

RAND_MAX=2147483647
804289383
846930886
1681692777
1714636915
1957747793
424238335
719885386
1649760492
596516649

Não é um processo verdadeiramente aleatório
Múltiplas execuções produzem exatamente a mesma sequência!

Explicação

A função rand() utiliza um algoritmo determinístico
Cada valor é calculado como função matemática do anterior
- a implementação usa variável de estado global;
- o seu valor é alterada cada vez que geramos num novo número
A sequência gerada repete-se eventualmente após um período muito longo

Gerar valores num intervalo

A função rand() produz sempre resultados entre 0 e RAND_MAX
Podemos transformar o resultado para obter valores noutros intervalos

Exemplo:

simular o lançamento de uma moeda
contabilizar o número de vezes que saiu cara ou coroa

Lançar uma moeda

Solução 1: Dividir o intervalo [0,RAND_MAX] a meio.

if (rand() < RAND_MAX/2) {
   cara ++; /* saiu cara */
} else {
   coroa ++; /* saiu coroa */
}

Solução 2: Usar o resto da divisão por 2.

if (rand()%2 == 0) {
   cara ++; /* saiu cara */
} else {
   coroa ++ /* saiu coroa */
}

Lançar uma moeda (2)

Simulando 1 milhão de lançamentos.

Solução 1: 499990 caras, 500010 coroas
Solução 2: 500155 caras, 499845 coroas

Cara e coroa deviam sair com igual probabilidade
Mas a 2ª solução resultou numa pior distribuição (sairam mais vezes caras)

Generalizando

Para obter um valor entre 0 e \(N-1\) podemos usar o resto de divisão por \(N\):

rand() % N

Produz resultados estatisticamente aceitáveis
Mas não produz a melhor distribuição
- alguns valores ocorrem mais frequentemente
- http://c-faq.com/lib/randrange.html

Alternativas melhores

Solução 1: Converter o resultado de rand() num valor fracionário \([0,1[\) e multiplicar por \(N\):

(int)((double)rand() / ((double)RAND_MAX+1)*N)

Solução 2: Dividir o intervalo de 0 a RAND_MAX em aproximadamente \(N\) partes (sem usar virgula flutuante):

rand() / (RAND_MAX/N + 1)

Exemplos

Simular o lançamento de um dado; resultados entre 1 e 6.

d = 1 + rand() % 6;
    // OK mas tem pior distribuição

d = 1 + (int)((double)rand() /
              ((double)RAND_MAX+1)*6); 
    // Solução melhor (1)

d = 1 + rand()/(RAND_MAX/6 + 1);
    // Solução melhor (2)

Nota: para um jogo simples a primeira solução será suficiente!

Colecionar estatísticas

Lançar um dado várias vezes e calcular qual o valor médio: \[ \text{valor médio} = \frac{\sum\text{valores obtidos}}{\text{número de lançamentos}} \]

Valor médio

#include <stdio.h>
#include <stdlib.h>
#define N 1000000  // 1 milhão de lançamentos

int main(void) {
    double soma = 0.0;
    int i, d;

    for (i = 0; i<N; i++) {
       d = 1 + rand()%6;
       soma += (double)d;
    }
    printf("Valor médio: %.15f\n", soma/N);
}

Execução

$ gcc -o dado1 dado1.c
./dado1
valor médio= 3.498953000000000

Quando simulamos mais lançamentos o resultado aproxima-se de 3.5. Porque será?

Justificação

Se o dado não é "viciado", cada face vai sair o mesmo número de vezes quando o número de lançamentos tende para \(\infty\)
Matematicamente diz-se que segue uma distribuição uniforme em que cada face tem igual probabilidade \(\frac{1}{6}\)

Justificação (cont.)

Com \(n\) lançamentos cada face sai aproximadamente \(\frac{n}{6}\) vezes; logo:

\[ \begin{aligned} s & \approx \frac{n}{6}\times 1 + \frac{n}{6}\times 2 + \frac{n}{6}\times 3 + \frac{n}{6}\times 4 + \frac{n}{6}\times 5 + \frac{n}{6}\times 6 \\ & = \frac{n}{6}\times (1+2+3+4+5+6) \\ & = \frac{n}{6}\times 21 = \frac{7n}{2} \end{aligned} \]

O valor médio será então: \(s/n = \left(\frac{7n}{2}\right)/n = \frac{7}{2} = 3.5\)

Exercício

Substituir a fórmula para gerar o valor do dado pelas com melhor distribuição

    d = 1 + (int)((double)rand() /
              ((double)RAND_MAX+1)*6); 
              
    d = 1 + rand()/(RAND_MAX/6 + 1);

Verificar o efeito sobre o valor médio calculado.

Repetibilidade

O gerador de pseudo-aleatórios é determinístico
- o próximo valor é calculado a partir de uma "semente"
- a "semente" é uma variável de estado global
Repetimos a sequência se começarmos da mesma semente
Podemos re-inicializar a semente usando a função

void srand(unsigned int);

Exemplo

#include <stdio.h>
#include <stdlib.h>

int main(void) {
   srand(1);  // iniciar a semente
   for (int i = 0; i<5; i++)
      printf("%d\n", rand());
   printf("\n");

   srand(1);  // re-inicializar a semente
   for (int i = 0; i<5; i++)
      printf("%d\n", rand());
}

Execução

Repete a sequência de 5 pseudo-aleatórios:

Porquê repetibilidade?

Facilita a reprodução das condições de execução
- podemos repetir exatamente os mesmos valores obtidos por rand()
- permite repetir a simulação de eventos (pseudo)aleatórios
Podemos "simular" imprevisibilidade inicializando a semente com um valor que depende do relógio

Simular imprevisibilidade

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int i;
    srand((unsigned)time(NULL));
      // time(NULL) retorna o
      // número de segundos desde 1 Jan 1970
    for (i = 0; i<5; i++)
       printf("%d\n", rand());
}

Estimar probabilidades

Podemos usar pseudo-aleatórios para correr simulações e estimar probabilidades
Vamos aproximar um probabilidade calculando a frequência: \[ \text{frequência} = \frac{\text{número de casos favoráveis}}{\text{número de experiências}} \]
Exemplo: qual a probabilidade de a soma de dois dados dar 7 ou 8?

Estimar probabilidades

#define N 1000000 // 1 milhão de experiências

int dado(void);   // função auxiliar

int main(void) {
  int i, d1, d2, conta = 0;
  for(i = 0; i<N; i++) {
    d1 = dado(); 
    d2 = dado();
    if(d1+d2 == 7 || d1+d2 == 8)
      conta ++;
  }
  printf("Soma 7 ou 8: %.15f\n", 
         (double)conta/(double)N);
}

Função auxiliar

/* Simular o lançamento de um dado */
int dado(void) {
    return 1 + rand()%6;
}

Resultados

Soma 7 ou 8:  0.305117000000000

Enumerando todos os 36 casos dos dois dados (verificar):
- 6 casos em que a soma dá 7
- 5 casos em que a soma dá 8
A probabilidade exata será então: \[ 6\times \frac{1}{36} + 5 \times \frac{1}{36} = \frac{11}{36} \approx 0.305555555555555 \]

Números pseudo-aleatórios

Pedro Vasconcelos, DCC/FCUP

Outubro 2019

Números pseudo-aleatórios

Pseudo-aleatórios em C

Exemplo

Execução

Explicação

Gerar valores num intervalo

Lançar uma moeda

Lançar uma moeda (2)

Generalizando

Alternativas melhores

Exemplos

Colecionar estatísticas

Valor médio

Execução

Justificação

Justificação (cont.)

Exercício

Repetibilidade

Exemplo

Execução

Porquê repetibilidade?

Simular imprevisibilidade

Estimar probabilidades

Estimar probabilidades

Função auxiliar

Resultados