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:
xi+1 = (A · xi + C) mod M
onde "x0" é 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 x0=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
...
Os geradores congruentes lineares são considerados fracos, por serem facilmente previsíveis. Por isso, não devem ser usados em aplicações críticas, como a criptografia.
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) ;
Caso a função ''lcrandom_parms'' não seja invocada, a implementação deve usar os valores default dos parâmetros A, C e M definidos no exemplo acima.
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 -----------------------------------------------------
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 106 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 |*********************
+----+----+----+----+----+----+----+----+----+----+
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 x0=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 x0=0.
Para os valores default de (A=40692, C=127 e M=10000000), o período do gerador é 62.503.
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 (230) -- valores tomados de LCG.
Para esses valores de A, C e M, o período do gerador deve ser igual a M.
Caso encontre erros do tipo ''relocation truncated to fit: R_X86_64_PC32 against symbol ...'' ao compilar seu código, experimente usar as opções ''-fPIC'' ou ''-mcmodel=medium'' na linha de compilação. Esses erros podem ocorrer no cálculo do período, caso um vetor seja muito grande.
Alternativamente, declare o vetor fora de main(), para que ele seja alocado como uma variável estática, e não seja alocado na pilha de main().
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.
Lembre-se de:
Identificar TODOS os seus arquivos (comentário com nome completo e GRR na primeira linha de cada arquivo).
Compilar com a opção ''-Wall'' e resolver todos os warnings, pois eles influem na nota.
Código sem comentários adequados será penalizado.