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