random pas si random que ça

**Biosox** · 31/07/2006, 14h59

Selon la FAQ C, voici comment obtenir un nombre aleatoire entre 0 et N-1
Je cite:

#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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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:

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
random = (int)(0.5+((float)rand() / RAND_MAX * (MAX)));
		if(random==MAX)
		{
			random=0;
		}

Et j'obtient:

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!

**salseropom** · 31/07/2006, 16h26

Salut, je ne comprends pas bien tes résultats : tu fais 100000 tirages et les chiffres de 0 à 8 sortent plus de 100000 fois... peut-être ai-je mal compris ton algo.
Je l'ai donc refait et j'obtiens des résultats différents des tiens :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
#include <stdlib.h>
#include <stdio.h>
 
#define VALMAX 10
#define NBTIRAGES 100000
 
int main()
{
  int tirage[NBTIRAGES],nbtirages[VALMAX],i,j;
  int nbrand;
 
  for(i=0;i<NBTIRAGES;i++)
  {
    nbrand = (int)((float)rand() / RAND_MAX * (VALMAX )); /* ici j'ai misVALMAX et non VALMAX-1 */
    tirage[i]=nbrand;  
  }
 
  for(i=0;i<VALMAX;i++)
  {
    nbtirages[i]=0;
    for(j=0;j<NBTIRAGES;++j)
      if(tirage[j]==i) nbtirages[i]++;
 
    printf("tirage[%d] = %d\n",i,nbtirages[i]);
  }
 
  return EXIT_SUCCESS;
}

et voici ma sortie

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
tirage[0] = 9993
tirage[1] = 9932
tirage[2] = 10189
tirage[3] = 10016
tirage[4] = 9908
tirage[5] = 10044
tirage[6] = 9959
tirage[7] = 9925
tirage[8] = 10017
tirage[9] = 10017

Mes résultats ne sont pas trop absurdes

**Biosox** · 31/07/2006, 16h45

Envoyé par salseropom

Salut, je ne comprends pas bien tes résultats : tu fais 100000 tirages et les chiffres de 0 à 8 sortent plus de 100000 fois... peut-être ai-je mal compris ton algo.

En effet, c'est parce qu'entre le moment ou j'ai commencé a ecrire mon post, je suis passé à 1000000 de tirages et je ne l'ai pas édité. Je vais l'éditer de ce pas.

J'ai essayé ton code: il fonctionne, mais il y a deux choses à redire:

1: tu as mis VALMAX et non VALMAX-1 pour que ça marche, ce qui confirme ce que je pense: il y a une erreur dans la FAQ.

2: tu ne vérifie pas si "VALMAX" sors au tirage. J'ai donc édité ton code et paf! c'est la problème: la valeur 10 sors (rarement mais elle sors):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <stdlib.h>
#include <stdio.h>

#define VALMAX 10
#define NBTIRAGES 100000

int main()
{
  int tirage[NBTIRAGES],nbtirages[VALMAX+1],i,j;
  int nbrand;
  
  for(i=0;i<NBTIRAGES;i++)
  {
    nbrand = (int)((float)rand() / RAND_MAX * (VALMAX )); /* ici j'ai misVALMAX et non VALMAX-1 */
    tirage[i]=nbrand;  
  }
  
  for(i=0;i<VALMAX+1;i++)
  {
    nbtirages[i]=0;
    for(j=0;j<NBTIRAGES;++j)
      if(tirage[j]==i) nbtirages[i]++;
      
    printf("tirage[%d] = %d\n",i,nbtirages[i]);
  }
  
  return EXIT_SUCCESS;
}

j'obtient:

tirage[0] = 9901
tirage[1] = 10076
tirage[2] = 9746
tirage[3] = 9967
tirage[4] = 10081
tirage[5] = 9974
tirage[6] = 10253
tirage[7] = 9805
tirage[8] = 10197
tirage[9] = 9994
tirage[10] = 6
Press any key to continue

Donc on a juste repoussé le problème:
on avait (avec VALMAX-1):
"je veux des nombres aléatoires uniformément répartits entre 0 et 9, mais malheureusement le 9 ne sors pas aussi souvent que les autres"
et on a (avec VALMAX)
"je veux des nombres aléatoires uniformément répartits entre 0 et 9, et il semble que c'est le cas, mais malheureusement le 10 sors aussi de temps à autre"

c'est pour ça que j'ai voulu corriger le cast plutot que de changer les bornes du domaine de définition...

**Foobar1329** · 31/07/2006, 17h07

Hello,

Envoyé par Biosox

Selon la FAQ C, voici comment obtenir un nombre aleatoire entre 0 et N-1
Je cite:

est supposé donner une répartition équiprobable des éléments de l'ensemble [0..N-1]

Selon les auteurs du Numerical Recipes in C, c'est
(int)((double)rand() / ((double)RAND_MAX + 1) * N)
toujours pour un nombre compris entre 0 et N-1.

Cela a son importance :
Dans le premier cas, avec
(int)((float)rand() / RAND_MAX * (N - 1)
Pour simplifier, c'est equivalent à (N-1)*fct où 0.0 <= fct <= 1.0
Mais pour que le facteur fct soit égal à 1, il est impératif que la valeur sortie par rand() soit RAND_MAX, ce qui ne doit pas arriver très fréquemment (Question à se poser : que vaut RAND_MAX sur l'implémentation et quelle est la probabilité de sortie de RAND_MAX par rand() pour 100000 tirages ?). La conséquence en est que tu vas souvent obtenir un nombre (N-1)*fct où 0.0 <= fct <= 0.99~~, soit ici 9*[0.0~~;0.99~~], donc souvent un nombre dans l'intervalle [0..8] (à cause du cast en int, qui va ramener à la partie entière du flottant et non pas à l'entier le plus proche.

Dans le second cas, avec
(int)((double)rand() / ((double)RAND_MAX + 1) * N)
Pour simplifier, c'est equivalent à N*fct où 0.0 <= fct <= 0.99~~. Et oui, on divise ce qui est généré par rand() par (RAND_MAX+1), pour ne pas jouer avec justement ce problème à la limite de devoir récupérer 1.0 pour générer le denier nombre de l'intervalle souhaité.
Ici, on évolue dans 10*[0.0~~;0.99~~], (donc entre 0.0~~ et 9.99~~ ) et au cast final, on récupère bien un nombre entre 0 et 9.

[coupé]

Envoyé par Biosox

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
random = (int)(0.5+((float)rand() / RAND_MAX * (MAX)));
		if(random==MAX)
		{
			random=0;
		}

Et j'obtient:

ç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?

Celle proposée plus haut (source : NR).

Envoyé par Biosox

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!

Bravo, tu as trouvé une boulette dans la FAQ et tu avais bien cerné le problème.

A+

**Biosox** · 31/07/2006, 17h20

Merci pour ces précisions, et bravo pour la qualité de tes explications!

J'ai tout compris!

Testé et approuvé!

**Emmanuel Delahaye** · 31/07/2006, 17h36

Envoyé par Biosox

Selon la FAQ C, voici comment obtenir un nombre aleatoire entre 0 et N-1

Effectivement, la formule de la FAQ n'est pas bonne. Bien vu. :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
Methode naive (Modulo)
[ 0] = 9929
[ 1] = 9972
[ 2] = 9946
[ 3] = 9874
[ 4] = 9841
[ 5] = 10084
[ 6] = 10193
[ 7] = 9969
[ 8] = 10211
[ 9] = 9981
 
random() de Borland C
[ 0] = 9872
[ 1] = 10134
[ 2] = 10044
[ 3] = 9982
[ 4] = 10197
[ 5] = 10155
[ 6] = 9877
[ 7] = 9929
[ 8] = 9868
[ 9] = 9937
 
FAQ DVP
[ 0] = 10979
[ 1] = 11270
[ 2] = 11179
[ 3] = 11003
[ 4] = 11382
[ 5] = 11071
[ 6] = 11112
[ 7] = 11100
[ 8] = 10902
[ 9] = 2
 
FAQ fclc
[ 0] = 9861
[ 1] = 9875
[ 2] = 10040
[ 3] = 9891
[ 4] = 9897
[ 5] = 10022
[ 6] = 10109
[ 7] = 10231
[ 8] = 10003
[ 9] = 10071
 
Press ENTER to continue.

avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
/* http://mapage.noos.fr/clib/ed/inc/random.h */
#include "ed/inc/random.h"
 
#define NB_TIRAGES 100000
#define MAX 9
 
static void clr_count (unsigned long count[], size_t n)
{
   size_t i;
   for (i = 0; i < n; i++)
   {
      count[i] = 0;
   }
}
 
static void prt_count (char const *cmt, unsigned long const count[], size_t n)
{
   size_t i;
   printf ("%s\n", cmt);
   for (i = 0; i < n; i++)
   {
      printf ("[%2lu] = %lu\n", (unsigned long) i, count[i]);
   }
   printf ("\n");
}
 
int main ()
{
   unsigned long count[MAX + 1];
 
   srand ((unsigned) time (NULL));
 
   /*  % */
   {
      int i;
 
      clr_count (count, sizeof count / sizeof *count);
      for (i = 0; i < NB_TIRAGES; i++)
      {
         size_t n = (rand () % (MAX + 1));
         count[n]++;
      }
      prt_count ("Methode naive (Modulo)", count, sizeof count / sizeof *count);
   }
 
   /*  random Borland C */
   {
      int i;
 
      clr_count (count, sizeof count / sizeof *count);
      for (i = 0; i < NB_TIRAGES; i++)
      {
         size_t n = random (MAX + 1);
         count[n]++;
      }
      prt_count ("random() de Borland C", count, sizeof count / sizeof *count);
   }
 
   /*  FAQ DVP */
   {
      int i;
 
      clr_count (count, sizeof count / sizeof *count);
      for (i = 0; i < NB_TIRAGES; i++)
      {
         size_t n = (int)((float)rand() / RAND_MAX * (MAX + 1 - 1));
         count[n]++;
      }
      prt_count ("FAQ DVP", count, sizeof count / sizeof *count);
   }
 
   /*  FAQ fclc
          */
   {
      int i;
 
      clr_count (count, sizeof count / sizeof *count);
      for (i = 0; i < NB_TIRAGES; i++)
      {
         size_t n = (int)((double)rand() / ((double)RAND_MAX + 1) * (MAX + 1));
         count[n]++;
      }
      prt_count ("FAQ fclc ", count, sizeof count / sizeof *count);
   }
 
   return 0;
}