Discussion :

[odsen.s]

Bonjour à tous,

J'ai voulu effectuer quelques tests sur la génération de nombres pseudo-aléatoires en C.

J'ai testé différentes méthodes :

Les deux premières sont très connues, je les appelles respectivement méthode 1 et méthode 2 :

Code :

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

1
2
3
/* on genere un nombre entre 0 et N */
int methode_1 = rand() % (N+1);
int methode_2 = (int)(rand() / (double)RAND_MAX * (N+1);

La troisième, que j'ai trouvée sur la FAQ, est sensée éviter certains défauts contenus dans les deux premières méthodes qui génèrent certains nombres de façon non aléatoire :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* methode 3 */
int alea(int n)
{
   int partSize   = (n == RAND_MAX) ? 1 : 1 + (RAND_MAX - n)/(n+1);
   int maxUsefull = partSize * n + (partSize-1);
   int draw;
 
   do
   {
      draw = rand();
   } while (draw > maxUsefull);
 
   return draw/partSize;
}

Le but de mes tests était de trouver laquelle de ces trois méthodes se rapprochait le plus de la situation d'équiprobabilité (un nombre a autant de chances qu'un autre de sortir).

Voici comment je procède :

Je choisis un nombre N (par exemple 9), les nombres tirés seront compris entre 0 et 9.
Avec chaque méthode, je fais un grand nombre de tirages (10 000, 1M, ...), et je compte les occurences de chaque nombre généré.
Je calcule ensuite la fréquence d'apparition de chaque nombre.
Je calcule le total des écarts (que j'appelle d) entre les fréquences d'apparition des nombres et la fréquence d'apparition parfaite (exemple, avec N = 9 et 10 000 tirages, la fréquence parfaite est de 10/10 000 = 1.0E-03)

La meilleure méthode est celle qui donne un nombre d le plus petit, car elle s'approche le plus de la situation d'équiprobabilité.

Pour ne pas me focaliser sur un résultat, j'effectue mille fois ce test, et je compte le nombre de fois que la méthode 1 avait le d le plus petit, idem pour la méthode 2 et 3.

C'est ces résultats qui m'ont surpris : aucune des trois méthodes n'offre un écart certain par rapport aux deux autres. Si j'avais eux sur 1000 tests la "méthode 3" 900 fois gagnante, j'aurais conclu qu'elle est réellement plus efficace. Mais les résultats ne montrent pas qu'une méthode est meilleure que l'autre.

Qu'en pensez-vous ? Avez-vous déjà effectué des tests similaires ?

Peut-être ma méthode de test n'est pas bonne ? (Je veux parler de la méthode en elle même, car je suis sûr de mon code, j'ai fait des vérifications à la calculette sur les tests).

Merci

[Jean-Marc.Bourguet]

Ces écarts suivent des lois connues (dont la fameuse "loi des grands nombres"). Arriver à l"équidistribution parfaite est fortement improbable.

Si tu veux tester l'équiprobabilité avec ces 3 transformations, je te suggère une expérience avec un générateur très simple (qui est équiprobable, c'est sa seule qualité)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
#define MY_RAND_MAX  10
 
static int seed = 0;
 
int mysrand(int s) {
   seed = s%(MY_RAND_MAX+1);
}
 
int myrand() {
   seed = (seed+1) % (MY_RAND_MAX+1);
   return seed;
}

et regarde ce qui se passe quand tu essaies de ramener sur 0-9 (le choix de MY_RAND_MAX est fait pour que le problème soit à son paroxysme).

[odsen.s]

Bonjour Jean-Marc,

J'ai testé ton générateur de cette façon :

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
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <time.h>
 
#define N 9
#define NB_TIRAGES 1000
#define MY_RAND_MAX  10
 
static int seed = 0;
 
int mysrand(int s) {
   seed = s%(MY_RAND_MAX+1);
}
 
int myrand() {
   seed = (seed+1) % (MY_RAND_MAX+1);
   return seed;
}
 
int main(void)
{
   size_t i;
   unsigned long compteur[N+1] = { 0 };
 
   mysrand(time(NULL));
 
   /* generation des nombres */
   for(i = 0; i < NB_TIRAGES; i++)
   {
      compteur[myrand() % (N+1)]++;
   }
 
   /* affichage des resultats */
   for(i = 0; i < N+1; i++)
   {
      printf("%d : %ld\n",i,compteur[i]);
   }
 
   return 0;
}

Le chiffre 0 est tiré 2 fois plus souvent que les autres chiffres. C'est ça le problème que tu voulais me montrer ?

Quelle est la cause exacte du problème ?

Ces écarts suivent des lois connues (dont la fameuse "loi des grands nombres"). Arriver à l"équidistribution parfaite est fortement improbable.

Il n'est donc pas possible de tester les trois méthodes de cette façon, en calculant les écarts ? Comment vérifier laquelle est la meilleure alors ?

Merci.

[Jean-Marc.Bourguet]

Le chiffre 0 est tiré 2 fois plus souvent que les autres chiffres. C'est ça le problème que tu voulais me montrer ?

Gagné. Ca ne se passe pas avec la troisième méthode.

Quelle est la cause exacte du problème ?

http://fr.wikipedia.org/wiki/Principe_des_tiroirs

[odsen.s]

Super, je te remercie
Bon week end.

[sebdu94]

Peut tu m'expliquer comment fonctionne la deuxième méthode.

Est-il possible de choisir les bornes ?

Merci

[odsen.s]

Salut,

Pour fixer les bornes min et max :

Code :

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

(int)((double)rand() / ((double)RAND_MAX + 1) * (max+1-min)) + min;

Pour le fonctionnement, je ne suis pas sûr, je préfère ne rien avancer.
Si quelqu'un a l'explication

[sebdu94]

Merci et pour la troisième méthode qui est apparemment plus efficace, est ce possible ?

[odsen.s]

C'est sans doute possible, mais comme je ne sais pas exactement comment fonctionne la fonction, je préfère ne rien avancer.

[sebdu94]

Daccord merci beaucoup.

[sebdu94]

Personne ne sait comment générer des nombres entre 1 et 52 avec la 3ème méthode ?

[gl]

Personne ne sait comment générer des nombres entre 1 et 52 avec la 3ème méthode ?

D'apres toi a quoi sert le parametre n de la fonction de la troisieme methode ?

[sebdu94]

Merci en fait j'ai trouvé,
le n sert a déterminé le nombre maximum.
et j'ai mis +1 sur la ligne qui tire aléatoirement pour commencer à 1.

Mais j'ai un problème avec cette méthode.
A chaque fois que je redémarre le programme, il me tire les mêmes chiffre.

Est ce normal ? Et existe-t-il une autre fonction ?

[Jean-Marc.Bourguet]

http://c.developpez.com/faq/c/?page=...ES_random_init

[Emmanuel Delahaye]

A chaque fois que je redémarre le programme, il me tire les mêmes chiffre.

Est ce normal ? Et existe-t-il une autre fonction ?

http://emmanuel-delahaye.developpez.com/notes.htm#rand