Geração de números aleatórios

Números aleatórios são muito importantes em várias áreas da informática, como jogos, simulações e na geração de chaves criptográficas. Um gerador de números pseudoaleatórios (PRNG - Pseudo Random Number Generator) é um algoritmo que gera uma sequência de valores aparentemente aleatórios. A sequência de números gerada por um PRNG não é realmente aleatória, porque pode ser reproduzida caso seja usado o mesmo valor inicial, usualmente chamado de "semente" (seed). A reprodução da sequência pseudoaleatória não é um bug, mas uma característica útil, caso se deseje repetir os valores usados em uma simulação, ou repetir os passos que levaram o programa a um erro, por exemplo.

Uma das abordagens mais simples para a geração de números pseudoaleatórios são os geradores congruentes lineares (LCG), que são definidos através da seguinte fórmula:

x_i+1 = (A · x_i + C) mod M

onde "x₀" é o valor inicial (semente), A e C são parâmetros inteiros, M é o tamanho do espaço de valores aleatórios possíveis e "mod" é o resto da divisão inteira.

Por exemplo, escolhendo-se A=40692, C=127, M=10000000 e x₀=0, será gerada a seguinte sequência de números pseudoaleatórios:

  x_0 = 0
  x_1 = 127
  x_2 = 5168011
  x_3 = 6703739
  x_4 = 8547515
  x_5 = 5480507
  x_6 = 2790971
  x_7 = 192059
  x_8 = 5264955
  x_9 = 1548987
  ...

Atividade

a) Implementação do módulo gerador de números aleatórios

Construa um módulo, que chamaremos de LC-Random, para gerar números inteiros pseudoaleatórios usando o algoritmo de congruência linear.

A interface do módulo é definida pelo seguinte arquivo de cabeçalho, que não deve ser alterado:

// ATENCAO: ESTE ARQUIVO NAO DEVE SER ALTERADO!

// calcula e devolve um valor pseudoaleatório
unsigned long lcrandom () ;

// define o valor inicial (semente) da sequência de aleatórios
// zero (0) por default
void lcrandom_seed (unsigned long s) ;

// informa o valor máximo que pode ser gerado (o mínimo é sempre zero)
unsigned long lcrandom_max () ;

// modifica os parâmetros da equação do gerador; por default
// devem ser usados: A=40692, C=127 e M=10000000
void lcrandom_parms (unsigned long A, unsigned long C, unsigned long M) ;

Dicas para a implementação:

• Os valores da semente, de x e dos parâmetros A, C e M são parte do estado interno do módulo e por isso devem ser declaradas como variáveis globais no arquivo ''lcrandom.c''. O estado interno deve ser invisível fora do módulo do gerador de números.

• O módulo apenas calcula, atualiza e devolve valores; por isso, nenhuma função de entrada/saída (''printf'', ''scanf'', etc) deve ser chamada dentro da implementação de suas funções (a não ser para produzir eventuais mensagens de erro).

• Reveja a aula sobre organização de código.

O que deve ficar em qual arquivo?

lcrandom.h

// lcrandom.h -----------------------------------------------------

// ATENCAO: ESTE ARQUIVO NAO DEVE SER ALTERADO!

// calcula e devolve um valor pseudoaleatório
unsigned long lcrandom () ;

// define o valor inicial (semente) da sequência de aleatórios
// zero (0) por default
void lcrandom_seed (unsigned long s) ;

// informa o valor máximo que pode ser gerado (o mínimo é sempre zero)
unsigned long lcrandom_max () ;

// modifica os parâmetros da equação do gerador; por default
// devem ser usados: A=40692, C=127 e M=10000000
void lcrandom_parms (unsigned long A, unsigned long C, unsigned long M) ;

// EOF -----------------------------------------------------

lcrandom.c

// lcrandom.c -----------------------------------------------------

#include "lcrandom.h"

// declara as variáveis com escopo de visibilidade somente NESTE arquivo

static unsigned long A = 40692;
static unsigned long C = 127;
static unsigned long M = 10000000;
static unsigned long x = 0;


// calcula e devolve um valor pseudoaleatório
unsigned long lcrandom ()
{
   ...
};

// define o valor inicial (semente) da sequência de aleatórios
// zero (0) por default
void lcrandom_seed (unsigned long s)
{
   ...
};


// informa o valor máximo que pode ser gerado (o mínimo é sempre zero)
unsigned long lcrandom_max ()
{
   ...
};


// modifica os parâmetros da equação do gerador; por default
// devem ser usados: A=40692, C=127 e M=10000000
void lcrandom_parms (unsigned long A, unsigned long C, unsigned long M) ;
{
   ...
};

// EOF -----------------------------------------------------

histograma-1.c

// histograma-1.c -----------------------------------------------------

#include "lcrandom.h"

#define NUM 100

int main(void)
{
   int i, ... ;

   // inicializa gerador de acordo com enunciado
   lcrandom_parms ( 23 , 24 , 25 ) ;

   for (i=0; i < NUM; i++)
      vet[i] = lcrandom();

   // calcula valores normalizados
   ...

   // gera historgrama
   ...

  return 0;
}

// EOF -----------------------------------------------------

b) Geração de histograma

A distribuição dos valores produzidos por um gerador de números aleatórios pode ser avaliada visualmente através de um histograma. Existem outras métricas melhores para avaliar a qualidade de um PRNG, algumas delas são descritas em Random.org.

Escreva um programa C para gerar um histograma dos valores aleatórios produzidos por seu módulo.

Para isso:

• gere 10⁶ valores aleatórios no intervalo [0...99] (use ''lcrandom() % 100'');

• conte quantas vezes cada um dos 100 números possíveis foi gerado;

• normalize (ajuste) as contagens para intervalo [0..100], aplicando uma regra de três às contagens obtidas, na qual a maior contagem equivale a 100;

• plote o histograma resultante em um gráfico em modo texto; no eixo vertical estão os valores possíveis (de 0 a 99, neste exemplo); no eixo horizontal estão as frequências de ocorrência normalizadas.

Exemplo simplificado de histograma em modo texto (cada ''*'' vale 2 unidades):

     0   10   20   30   40   50   60   70   80   90   100
     +----+----+----+----+----+----+----+----+----+----+
   0 |*****************************
   1 |********************************
   2 |**************************
   3 |******************************
   4 |****************************
   5 |******************************
   6 |****************************
   7 |******************************
  ...|... 
  98 |***********************
  99 |*********************
     +----+----+----+----+----+----+----+----+----+----+

c) Cálculo de período

O período de um PRNG corresponde à quantidade de valores gerados por ele antes de começar a repetí-los, para uma dada semente.

Por exemplo, para uma semente x₀=0, um PRNG gera a seguinte sequência, cujo período é 16, pois são gerados 16 valores distintos antes de repetir o 7801:

0 2233 491 11 7219 7801 31 446 9876 831 6159 43259 63 38321 1126 43674 7801 31 446 9876 831 ...

Escreva um programa C para calcular o período do gerador implementado em seu módulo, a partir de x₀=0.

d) Tudo de novo, com novos parâmetros

Repita o cálculo do histograma e do período usando valores melhores para os parâmetros A, C e M do gerador: A = 1103515245, C = 12345 e M = 1073741824 (2³⁰) -- valores tomados de LCG.

Produtos por Entregar

Este projeto deve ser feito individualmente. Plágio não será tolerado e seu código será comparado com os de seus colegas e com os projetos entregues em semestres anteriores.

Cada warning decorrente da compilação incorre em desconto de 10%, computado com taxa composta.

Arquivos a entregar (por e-mail) ao professor:

• lcrandom.c : implementação das funções do gerador de aleatórios;

• histograma-1.c : implementação do histograma do gerador com os valores default de A, C e M;

• histograma-2.c : idem, com os valores melhores de A, C e M;

• periodo-1.c : implementação do cálculo de período do gerador com os valores default de A, C e M;

• periodo-2.c : idem, com os valores melhores de A, C e M.

Os nomes dos arquivos devem ser exatamente estes para que os testes possam ser automatizados. Empacote os arquivos com o comando

tar cvf USERNAME.tar lcrandom.c histograma-1.c histograma-2.c periodo-1.c periodo-2.c

Sendo USERNAME o seu username no DInf. Trabalhos entregues fora do especificado incorrerão em desconto de 50% da nota.