Números aleatórios

Nesta aula, vamos explorar a geração de números aleatórios em C. Números aleatórios são essenciais em simulações, jogos, criptografia e outros domínios. A biblioteca padrão de C fornece funções para gerar números pseudo-aleatórios, mas é fundamental entender suas limitações e como utilizá-las corretamente.

Começaremos com as funções rand e srand, discutiremos o conceito de semente, as limitações do gerador padrão e, por fim, como obter distribuições específicas, como uniforme, normal e outras.

rand e srand

A função rand() retorna um inteiro pseudo-aleatório entre 0 e RAND_MAX, uma constante definida na biblioteca <stdlib.h> (geralmente 32767). Ela gera uma sequência de números que parece aleatória, mas é determinística: dado o mesmo estado inicial, a sequência será a mesma.

Para inicializar o gerador, usamos a função srand(), que define a semente (seed). A semente é um número inteiro que determina o estado inicial do gerador. Se você chamar srand() com a mesma semente, a sequência de rand() será idêntica. Para obter sequências diferentes a cada execução, é comum usar o tempo atual como semente, por exemplo, srand(time(0)).

Exemplo básico:

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

int main() {
    srand(time(0)); // inicializa com o tempo atual
    printf("%d\n", rand()); // imprime um número aleatório
    printf("%d\n", rand()); // outro número
    return 0;
}

Sem chamar srand(), o gerador é inicializado com semente 1, então a sequência será sempre a mesma em cada execução.

Semente

A semente é um valor inteiro que define o ponto de partida da sequência pseudo-aleatória. A função srand() aceita um unsigned int como argumento. A escolha da semente é crucial: se você usar a mesma semente, obterá a mesma sequência, o que pode ser útil para reproduzir experimentos, mas indesejável em jogos ou aplicações que exigem imprevisibilidade.

Uma prática comum é usar o tempo atual como semente, mas isso pode ser previsível em sistemas com alta resolução de tempo. Para aplicações mais robustas, pode-se combinar múltiplas fontes de entropia, como endereço de memória, ID de processo, etc.

Exemplo de inicialização com diferentes sementes:

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

int main() {
    srand(42); // semente fixa
    printf("%d %d %d\n", rand(), rand(), rand());

    srand(time(0)); // semente variável
    printf("%d %d %d\n", rand(), rand(), rand());
    return 0;
}

Observe que com semente fixa, a saída é sempre a mesma, enquanto com o tempo varia.

Limitações

O gerador rand() tem várias limitações:

• Baixa qualidade: É um gerador linear congruencial, que pode apresentar correlações entre números gerados. Para simulações científicas ou criptografia, não é adequado.
• Faixa limitada: RAND_MAX é geralmente 32767, o que limita a faixa de números gerados.
• Distribuição não uniforme: Se você usar o operador módulo (%) para obter números em um intervalo menor, a distribuição pode ser viciada, especialmente se o intervalo não dividir exatamente RAND_MAX+1.
• Previsibilidade: Se a semente for conhecida, a sequência pode ser reproduzida. Isso é inaceitável para segurança.

Exemplo de viés com módulo:

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

int main() {
    // Suponha RAND_MAX = 32767, queremos números 0-9
    int freq[10] = {0};
    for (int i = 0; i < 10000; i++) {
        int r = rand() % 10;
        freq[r]++;
    }
    for (int i = 0; i < 10; i++) {
        printf("%d: %d\n", i, freq[i]);
    }
    return 0;
}

Para evitar o viés, podemos usar técnicas como rejeição ou usar geradores melhores, como random() em sistemas POSIX, ou bibliotecas como std::mt19937 em C++ (mas estamos em C).

Distribuição

Em muitas aplicações, precisamos de números aleatórios com uma distribuição específica, não apenas uniforme. A função rand() gera uma distribuição uniforme em [0, RAND_MAX]. Para obter outras distribuições, precisamos transformar esses números.

Distribuição uniforme em [a, b]: Podemos usar a fórmula a + (rand() % (b - a + 1)), mas isso sofre do viés mencionado. Uma alternativa melhor é usar a + (int)((double)rand() / (RAND_MAX + 1.0) * (b - a + 1)).

Distribuição normal: Podemos usar o método de Box-Muller, que transforma duas variáveis uniformes em duas variáveis normais padrão.

Exemplo de distribuição uniforme melhorada:

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

int rand_range(int a, int b) {
    return a + (int)((double)rand() / (RAND_MAX + 1.0) * (b - a + 1));
}

int main() {
    for (int i = 0; i < 10; i++) {
        printf("%d ", rand_range(1, 6)); // simula dado
    }
    printf("\n");
    return 0;
}

Para distribuição normal, um exemplo:

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

double rand_normal() {
    double u1 = (double)rand() / (RAND_MAX + 1.0);
    double u2 = (double)rand() / (RAND_MAX + 1.0);
    return sqrt(-2.0 * log(u1)) * cos(2.0 * M_PI * u2);
}

int main() {
    for (int i = 0; i < 10; i++) {
        printf("%f\n", rand_normal());
    }
    return 0;
}

Lembre-se de compilar com -lm para linkar a biblioteca matemática.

Boas práticas

Para a maioria das aplicações não críticas, rand() é suficiente, mas é importante:

• Sempre inicialize a semente com srand() para evitar sequências previsíveis.
• Evite o uso de % para gerar intervalos, pois introduz viés.
• Para aplicações que exigem alta qualidade, considere usar random() (POSIX) ou implementar um gerador melhor, como Mersenne Twister.
• Para criptografia, use funções específicas de geração de números aleatórios seguros, como getrandom() em Linux.

Referências

• cppreference: rand
• cppreference: srand
• Linux man page: rand
• GNU C Library: ISO Random
• Wikipedia: Linear congruential generator
• Wikipedia: Box-Muller transform
• C11 standard (n1570)

Exercícios

1. Escreva um programa que gere 10 números aleatórios entre 1 e 100, usando rand() e srand() com semente baseada no tempo.

Ver resposta

✓ Resposta:

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

int main() {
    srand(time(0));
    for (int i = 0; i < 10; i++) {
        printf("%d\n", 1 + rand() % 100);
    }
    return 0;
}

2. Explique por que usar rand() % n pode produzir uma distribuição não uniforme. Dê um exemplo em que isso acontece.

Ver resposta

✓ Resposta: Se RAND_MAX+1 não for múltiplo de n, os valores no início do intervalo têm probabilidade ligeiramente maior. Por exemplo, se RAND_MAX = 32767 e n = 10000, então os números 0-2767 têm chance extra de aparecer, pois há 32768 valores possíveis, e 32768 % 10000 = 2768, então os primeiros 2768 números têm um valor extra. Isso causa viés.
3. Crie uma função rand_double() que retorna um número de ponto flutuante aleatório entre 0.0 e 1.0 (exclusivo).

Ver resposta

✓ Resposta:

double rand_double() {
    return (double)rand() / (RAND_MAX + 1.0);
}

4. Usando o método de Box-Muller, gere 5 números com distribuição normal padrão (média 0, desvio padrão 1).

Ver resposta

✓ Resposta:

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

int main() {
    for (int i = 0; i < 5; i++) {
        double u1 = (double)rand() / (RAND_MAX + 1.0);
        double u2 = (double)rand() / (RAND_MAX + 1.0);
        double z = sqrt(-2.0 * log(u1)) * cos(2.0 * M_PI * u2);
        printf("%f\n", z);
    }
    return 0;
}

5. Pesquise sobre a função random() e srandom() no Linux. Escreva um programa que as utilize para gerar 5 números aleatórios entre 0 e 100.

Ver resposta

✓ Resposta:

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

int main() {
    srandom(time(0));
    for (int i = 0; i < 5; i++) {
        printf("%ld\n", random() % 101);
    }
    return 0;
}