random pas si random que ça
Selon la FAQ C, voici comment obtenir un nombre aleatoire entre 0 et N-1
Je cite:
Citation:
#include <stdlib.h>
int randomValue = (int)((float)rand() / RAND_MAX * (N - 1));
est supposé donner une répartition équiprobable des éléments de l'ensemble [0..N-1]
Seulement voila: je tente le coup pour voir si l'équiprobabilité est assez bien respectée: Je fixe N à MAX=10, je m'attend donc a avoir des "tirages" equiprobable dans [0..9].
Je crée un tableau de 10 int, que j'initialise tous à 0, et je fais 100000 tirages. a chaque tirage, j'incrémente la case du tableau dont l'indice a été tiré. a la fin, j'affiche toutes les cases du tableau et m'attends à ce que, grosso-modo, chaque case contienne 10000.
Mais ce n'est pas le cas: le 9 ne sort presque JAMAIS:
CODE:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define MAX 10
int main()
{
int tirage[MAX];
int i=0;
int random;
srand((int)time(NULL));
/* initie le tableau de tirage à 0 */
for(i=0;i<MAX;i++)
{
tirages[i] = 0;
}
/* fait plein de tirages */
for(i=0;i<1000000;i++)
{
random = (int)((float)rand() / RAND_MAX * (MAX - 1));
tirages[random]++;
}
for(i=0;i<MAX;i++)
{
printf("tirages[%d] = %d\n", i, tirages[i]);
}
return 0;
} |
et voici un exemple de sortie:
Citation:
tirage[0] = 111304
tirage[1] = 111396
tirage[2] = 110829
tirage[3] = 110854
tirage[4] = 110493
tirage[5] = 111001
tirage[6] = 111335
tirage[7] = 111532
tirage[8] = 111232
tirage[9] = 24
Press any key to continue
Selon ma compréhesion:
1) rand() donne une répartition uniforme de [0..RAND_MAX]
donc:
2) (float)rand() / RAND_MAX donne une repartition uniforme dans [0.0000, 1.0000]
avec un cast a float pour pas obtenir que les deux éléments 0 et 1 mais bien des nombres à virgules.
et enfin:
3) (int)((float)rand() / RAND_MAX * (N - 1))
donne un nombre aléatoire dans [0..N-1] (re-casté en int puisque c'est ce qu'on veut)
Et c'est bien lors de ce cast que le problème apparaît:
Pour obtenir un 9 apres le cast, il faut avoir un 9.0000 avant!
Mais pour obtenir par exemple un 3 apres, il faut un nombre compris entre 3.0000 et 3.9999...
Raison pour laquelle le 9 n'est presque jamais tiré.
Je veux donc corriger ce probleme de cast. Dans la F.A.Q, ils disent que pour arrondir un reel il faut lui ajouter +0.5 avant de le tronquer.
random = (int)(0.5+((float)rand() / RAND_MAX * (MAX)));
Mais a ce moment, 0 est tiré moitié moins souvent qu'avant, et 10 est tiré aussi (2X moins que les autres) alors qu'il ne devrait pas.
J'ai donc fait:
Code:
1
2
3
4
5
| random = (int)(0.5+((float)rand() / RAND_MAX * (MAX)));
if(random==MAX)
{
random=0;
} |
Et j'obtient:
Citation:
tirage[0] = 100173
tirage[1] = 99837
tirage[2] = 99854
tirage[3] = 100116
tirage[4] = 100224
tirage[5] = 99792
tirage[6] = 100468
tirage[7] = 100299
tirage[8] = 99678
tirage[9] = 99559
tirage[10] = 0
Press any key to continue
ça fonctionne mais c'est pas trèse élégant et on perd du temps avec un if a chaque fois.
Y-a-til une autre solution?
Ou est-ce que c'est moi qui fait tout faux?
p.s: est si t'arrive jusqu'ici c'est que tu m'as tout lu, merci!
