terça-feira, 31 de janeiro de 2012

rand8 usando rand5

Você tem a função rand5() que gera valores no seguinte intervalo [0,1,2,3,4] com mesma probabilidade. Com essa função rand5, você precisa construir rand8() que gera valores no intervalo [0,1,2,3,4,5,6,7] com mesma probabilidade para cada.

Idéia 1:
Somar 2 duas execuções do rand5() e aplicar a operação % 8.
int rand8(){
  return (rand5()+rand5())%8;
}

Observe que quando o as duas execuções de rand5() são somadas, o valor dessa soma varia entre 0 até 8. Quando aplicamos a operação módulo 8, o valor fica no intervalo esperado mas com o seguinte problema:

Tabela das soma possíveis

+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 5
2 2 3 4 5 6
3 3 4 5 6 7
4 4 5 6 7 8

Note que a distribuição dos valores não é igual para todos os valores de soma possível.

Número 0 1 2 3 4 5 6 7
Ocorrência 2 2 3 4 5 4 3 2

A situação só piora quando a função rand5() é chamada mais vezes. Considere a seguinte idéia:

Idéia 2:
int rand8(){
  int i,s;
  s = 0;
  for(i=0;i<7;i++)
    s = s + rand5();
  return s%8;
}


Usando este programa abaixo, podemos contar o número de ocorrência de cada número:

int s[8];/*numero de ocorrencia de cada numero do rand8*/ 
int sum_rand5(int n, int sum){
  int j;
  if(n<7){
    for(j=0;j<5;j++){
      sum_rand5(n+1,sum+j);
    }
  }else{
    printf("%d\n",sum%8);
    s[sum%8]++;
  }
}
int main(){
  int i;
  for(i=0;i<8;i++) s[i] = 0;
  sum_rand5(0,0);
  for(i=0;i<8;i++)
    printf("%d %d\n",i,s[i]);
}

A tabela com o número de ocorrência gerado por esse programa é esta aqui:

Número 0 1 2 3 4 5 6 7
Ocorrência 9766 9681 9646 9681 9766 9850 9885 9850

Idéia 3:

Vamos construir o rand2 a partir do rand5. Usando o rand2, podemos construir o rand8() através do sistema binário da seguinte maneira:

int rand2(){
 int z;
 do{
   z = rand5();
 }while(z==4);
 if(z<2) return 0;
 else return 1; 
}
int rand8(){
  return rand2() + 2*rand2() + 4*rand2();
}


Idéia 4:

Executando o rand5 duas vezes, teremos 25 valores possíveis. Se eliminarmos 1 dos
valores possíveis, teremos um número de possibilidades que é múltiplo de 8. Falta saber como combinar as duas chamadas para que a ocorrência dos números no
intervalo [0,7] fiquem distribuídos igualmente.

Realize a seguinte operação:
int rand8(){
  do{
   z = rand5()*5 + rand5();
  }while(z==24);
  return z%8;
}
Tabela das soma possíveis módulo 8

+%8 0 1 2 3 4
0 0 1 2 3 4
5 5 6 7 0 1
10 2 3 4 5 6
15 7 0 1 2 3
20 4 5 6 7 0


Número de ocorrência de cada número

Número 0 1 2 3 4 5 6 7
Ocorrência 4 3 3 3 3 3 3 3

Observe que se retirarmos o valor 24, todos os valores passarão a ter o mesmo número de ocorrência. Observe também para construir o rand2, temos que descartar o 1 valor de 5 possíveis para garantir a equiprobalidade e essa função terá que ser chamada três vezes. Enquanto que nessa solução, teremos que descartar 1 valor de 25 possíveis.

Análise do número de chamadas realizadas Idéia 4

Vamos analisar o número de chamadas realizadas pelo último algoritmo.
p = 24/25 (a probabilidade que as duas chamadas de rand5 não precise ser descartada)
q = 1/25 (a probabilidade que as duas chamadas de rand5 precisem ser descartadas)

O número esperado de chamadas do algoritmo é dado pela seguinte fórmula:

N = 2p + 4qp + 6q^2p+ 8q^3p + 10q^4p+...

double p = 24/25.0;
double q = 1/25.0;
double acumulado = 1;
double s = 0.0;
for(i=1;i<=7;i++){
     s = s + 2*i*acumulado*p;
     acumulado*=q;
}
printf("%lf\n",s);

Valor encontrado: 2,083333

Análise do número de chamadas realizadas Idéia 2

Vamos analisar o número de chamadas realizadas pelo último algoritmo.
p = 64/125(a probabilidade que as três chamadas de rand2 não precise ser descartada)
q = 61/125 (a probabilidade que as três chamadas de rand5 precisem ser descartadas)

O número esperado de chamadas do algoritmo é dado pela seguinte fórmula:

N = 3p + 6qp + 9q^2p+ 12q^3p + 15q^4p+...

O valor encontrado pelo programa acima: 5,859375

Um comentário:

Anônimo disse...

Esse foi o post mais lombrado que você colocou nesse site Wladmir.

David Sena