Números randômico e Geradores

Números randômicos e geradores

Uma maneira de gerar números pseudo-randômicos é através de funções da seguinte forma

seed(0) = 0

seed(n+1) = (seed(n) + STEP) % MOD

Essa função gera números pseudo-randômicos entre 0 e MOD-1. Se escolhermos os valores de STEP e MOD cuidadosamente, nós podemos gerar todos os valores no intervalo 0 até MOD-1. Caso contrário, obtermos apenas ciclos com um subconjunto dos valores no intervalo 0 até MOD-1. Um número é dito gerador quando o ciclo gerador por ele tem MOD números.

Considere o seguinte exemplo:

STEP = 3

MOD = 5

Sequência Gerada: 0,3,1,4,2,0,3,1,4,2,0,...

Tamanho do ciclo : 5

STEP = 5

MOD 20

Sequência: 0, 5,10,15,0,5,10,15,...

Tamanho do ciclo: 4

Considere o seguinte problema:
 Descobrir se para os valores de STEP e MOD, a função é geradora ou não?

Uma solução simples seria descobrir o tamanho do ciclo gerador pelo números. Para isso, basta guardar os valores da função a partir do valor inicial 0. Quando aparecer o primeiro número repetido, teremos o fim do ciclo.

int i,x;
  int values[MOD];
  for(i=0; i< MOD; i++)
   values[i] = 0;
  for(i=0;i<MOD;i++){
    x = seed(i);
    if(values[x]==0){
      printf("%d\n",seed(i));
      values[x]=1;
    }else{
      printf("tamanho %d\n",i);
      break;
    }
  }
  if(i==MOD){
    printf("gerador randomico uniforme\n");
  }else{
    printf("nao gerador\n");
  } 

Uma solução maravilhosamente simples existe para esse problema. Uma função é geradora se os valores STEP e MOD são primos entre si.

if(mdc(STEP,MOD)==1){
    printf("gerador randomico uniforme\n");
  }else{
    printf("nao gerador\n");
  }

Esse problema também ocorre na biologia :) . O processo evolutivo da cigarra selecionou como o tamanho do ciclo de vida das cigarras um número primo para protegê-la dos outros predadores.

Leia os seguintes textos:

http://amatematicaandaporai.blogspot.com/2009/03/cigarra-conhece-os-numeros-primos.html

http://www1.folha.uol.com.br/folha/ciencia/ult306u11973.shtml