Nombres aléatoires.

Version imprimable

Voir 40 message(s) de cette discussion en une page

22/12/2005, 12h44
casafa

Nombres aléatoires.

Bonjour,

J'ai trouvé ceci dans la FAQ sur les nombres aléatoires: http://c.developpez.com/faq/c/?page=..._random_bornes

Vous dites ceci: "Malheureusement, une telle méthode ne fournit pas, sauf pour des valeurs de N particulières, une répartition équiprobable des tirages."

1)Pourquoi la répartition n'est pas équiprobable ?
2)En C++, doit-on toujours utiliser la bibliothèque stdlib.h et les fonctions srand et rand pour tirer des nombres alétoires ?

Merci d'avance...
22/12/2005, 13h00
DaZumba

Re: Nombres aléatoires.

Citation:

Envoyé par casafa

Vous dites ceci: "Malheureusement, une telle méthode ne fournit pas, sauf pour des valeurs de N particulières, une répartition équiprobable des tirages."

Equiprobable n'est pas un bon mot, en effet. Il faudrait mieux dire "faiblement aleatoire". C'est pour la methode simple "rand() % N". Cette methode donne beaucoup d'importance aux bits de poids faible, qui sont connus pour ne pas etre tres aleatoire dans beaucoup de generateurs. Il est donc conseille de minimiser l'importance des bits de poids faible, ce que fait la deuxieme methode (mais cela reste un generateur pseudo-aleatoire, de toute facon).

Citation:

2)En C++, doit-on toujours utiliser la bibliothèque stdlib.h et les fonctions srand et rand pour tirer des nombres alétoires ?

Les braves gens du forum C++ (ou n'importe quel cours de C++, j'imagine), sauront repondre a cette question.
22/12/2005, 13h13
casafa

Merci de ta réponse mais je n'ai pas tout compris:

Pourquoi les bits de poids faible ne serait pas bien alétoire ? A cause de la fonction "rand()" ou à cause de l'expression "rand()%N" ?

Si c'est à cause de l'expression "rand()%N", j'aimerais bien comprendre mathématiquement pourquoi.
22/12/2005, 13h34
BugFactory

A cause de rand().

Cependant, il y a une autre raison pour laquelle le générateur ne serait pas équiprobable même si rand était parfait.

% est l'opérateur modulo, reste d'une division entière. On obtient donc simplement un nombre entre 0 et N. Dpendant, si la valeur maximum de rand() n'est pas un multiple de N-1, certains nombres ont plus de chances d'être tirés que d'autre.

Appelons M le nombre maximum que rand() puisse générer. Pour l'exemple, prenons 4. Et prenons N = 3.
Dans ce cas, les résultats possibles sont :
0 % 3 = 0
1 % 3 = 1
2 % 3 = 2
3 % 3 = 0
4 % 3 = 1
0 et 1 ont une chance de plus d'être tirés que 2.

Re: Nombres aléatoires.

Citation:

Envoyé par casafa

1)Pourquoi la répartition n'est pas équiprobable ?

La FAQ confond deux problemes.

1/ Pas mal de generateurs de nombres aleatoires simples ont des defauts qui se manifeste par le fait que les bits de poids faibles ne sont pas aleatoires (mais generalement equiprobables). Un exemple extreme serait d'alterner les nombres pairs et impairs. Utiliser

Code:

int randomValue = (int)((float)rand() / RAND_MAX * (N - 1));

plutot que

Code:

randomValue = rand() % N;

permet d'eviter ce probleme en prenant les bits de poids forts du nombre genere.

2/ rand genere des nombres equirepartit entre 0 et RAND_MAX inclus. Les deux procedures de choix d'un nombre entre 0 et N (non inclus cette fois), revienne a repartir les nombres entre 0 et RAND_MAX en N ensemble de taille egale si on veut aussi une equirepartition. Ce que ne font pas les procedures de la FAQ si RAND_MAX+1 n'est pas un multiple de N. (Pour le verifier, prenons RAND_MAX=15 et cherchons a avoir des nombres entre 0 et 10, la methode avec modulo favorise 0, 1, 2, 3, 4 et 5 qui seront tires deux fois plus souvent que 6, 7, 8 et 9; la methode avec les float favorise d'autres nombres mais en favorise aussi).

Pour eviter les deux problemes, il faut faire quelque chose du genre
Code:

1 2 3 4 5 6 7 8 9 10 11 int alea(int n) { assert (0 < n && n-1 <= RAND_MAX); int partSize = 1 + (RAND_MAX - (n-1)) / n; int maxUsefull = partSize * n; int draw; do { draw = rand(); } while (draw >= maxUsefull); return draw/partSize; }
(Les petites complications dans le calcul de partSize sont la pour traiter le cas ou RAND_MAX=INT_MAX).

Problemes supplementaires avec la proposition

Code:

int randomValue = (int)((float)rand() / RAND_MAX * (N - 1));

1/ Si RAND_MAX a plus de bits significatifs que ne peut en contenir un float, la conversion en float perds des bits aleatoires. Heureusement ce sont les moins significatifs mais ca peut entrainer un biais du genre ne generer que des nombres pairs.
2/ Avec les format float courant, si RAND_MAX n'est pas une puissance de 2 (cas quand meme courant vu que RAND_MAX est le plus grand nombre genere, avec les methodes courantes -- mais pas toutes -- RAND_MAX sera de 1 inferieur a une puissance de deux), la division n'est pas exactement representable et j'ai pas envie de chercher a savoir ce qui se passe quant a la repartition des tirages suite a cela.
Donc si on veut utiliser cette methode, il vaut mieux prendre

Code:

int randomValue = (int)((double)rand() / (RAND_MAX+1) * N);

Note: si tu tiens reellement a la qualite de ton generateur, tu etudies la literature en la matiere et tu en choisis un avec les qualites qu'il te faut.

Citation:

2)En C++, doit-on toujours utiliser la bibliothèque stdlib.h et les fonctions srand et rand pour tirer des nombres alétoires ?

Oui.

Re: Nombres aléatoires.

Citation:
Envoyé par Jean-Marc.Bourguet
Citation:

Envoyé par casafa

1)Pourquoi la répartition n'est pas équiprobable ?

La FAQ confond deux problemes.

2/ rand genere des nombres equirepartit entre 0 et RAND_MAX inclus. Les deux procedures de choix d'un nombre entre 0 et N (non inclus cette fois), revienne a repartir les nombres entre 0 et RAND_MAX en N ensemble de taille egale si on veut aussi une equirepartition. Ce que ne font pas les procedures de la FAQ si RAND_MAX+1 n'est pas un multiple de N. (Pour le verifier, prenons RAND_MAX=15 et cherchons a avoir des nombres entre 0 et 10, la methode avec modulo favorise 0, 1, 2, 3, 4 et 5 qui seront tires deux fois plus souvent que 6, 7, 8 et 9; la methode avec les float favorise d'autres nombres mais en favorise aussi).

Pour eviter les deux problemes, il faut faire quelque chose du genre
Code:

1 2 3 4 5 6 7 8 9 10 11 int alea(int n) { assert (0 < n && n-1 <= RAND_MAX); int partSize = 1 + (RAND_MAX - (n-1)) / n; int maxUsefull = partSize * n; int draw; do { draw = rand(); } while (draw >= maxUsefull); return draw/partSize; }
(Les petites complications dans le calcul de partSize sont la pour traiter le cas ou RAND_MAX=INT_MAX).
Ah j'suis content :), quelqu'un qui explique ce problème et résoud simplement (avec le do-while) comme moi j'l'ai fait, ya 2 ans, mais personne ne voulait m'écouter :/.

EDIT : En fait, j'ai lu assez vite, et j'suis pas sûr qu'on ait fait pareil.
Moi j'ai considéré le plus grand intervalle possible entre 0 et RAND_MAX tel que son cardinal soit toujours un multiple de 'n'.
Ainsi, on cherche le plus grand multiple de 'n' entre 0 et RAND_MAX.

Et donc on cherche uniquement les nombres compris entre 0 et ce multiple-1.
Et donc ainsi, on fait la méthode du modulo parce qu'on sait que les nombres que l'on tire ont meme probabilité de sortir car on a filtré les indésirables.

(je suis plus très sûr avec les +1 ou -1 pour les chiffres là).

Voilà le code que j'avais fait, c'était avec des congruences.
Certifié équiprobable si rand() est équiprobable.
Il tire un nombre entre a et b.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 int RandUnit(int a, int b) { int random; int rest = (RAND_MAX + 1) % (b - a + 1); do { random = rand(); } while (random > (RAND_MAX - rest)); return a + random % (b - a + 1); }

22/12/2005, 16h10
Jean-Marc.Bourguet

Re: Nombres aléatoires.

Citation:

Envoyé par HanLee

[Ah j'suis content :), quelqu'un qui explique ce problème et résoud simplement (avec le do-while) comme moi j'l'ai fait, ya 2 ans, mais personne ne voulait m'écouter :/.

Ca me semble etre la methode classique des gens qui comprennent le probleme ;-)

Citation:

Et donc ainsi, on fait la méthode du modulo parce qu'on sait que les nombres que l'on tire ont meme probabilité de sortir car on a filtré les indésirables.

Et donc tu as le probleme que tu utilises les bits de poids faibles qui sont trop souvent de moins bonne qualite que les bits de poids forts. C'est pour cela que je refais une division plutot qu'un modulo.
22/12/2005, 16h31
gege2061

Re: Nombres aléatoires.

Bonjour,

Citation:

Envoyé par Jean-Marc.Bourguet

Citation:

Envoyé par HanLee

[Ah j'suis content :), quelqu'un qui explique ce problème et résoud simplement (avec le do-while) comme moi j'l'ai fait, ya 2 ans, mais personne ne voulait m'écouter :/.

Ca me semble etre la methode classique des gens qui comprennent le probleme ;-)

sauf qu'il y a un risque de boucle infinie :D
Avec un bon générateur de nombre, c'est très peu probable qu'il nous sorte une suite de nombres infinis en entre RAND_MAX - rest et RAND_MAX (pour reprendre le code de HanLee). Par contre avec un générateur bancal rien n'est impossible :(
22/12/2005, 16h38
Jean-Marc.Bourguet

Re: Nombres aléatoires.

Citation:

Envoyé par gege2061

sauf qu'il y a un risque de boucle infinie :D

Si tu as un generateur si mauvais que son RAND_MAX n'est jamais genere, je me demande s'il ne vaut mieux pas que ca boucle indefiniment :D

Edit: a la place de "son RAND_MAX" lire "les nombres entre 0 et RAND_MAX/2", merci.

Merci pour toutes vos réponses.

Je vien de réaliser un programme qui me calcul la qualité d'un générateur de nombre aléatoire.

J'ai utilisé l'écart-type pour calculer la qualité du générateur de nombre aléatoire, est-ce une bonne idée ?

Voici mon programme:
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 37 38 39 40 41 42 43 44 #include <stdlib.h> #include <stdio.h> #include <math.h> #include <assert.h> int alea(int n){ //1 //int randomValue = (int)((double)rand() / (RAND_MAX+1) * n); //return (randomValue); //2 //return randomValue; //return (rand()%n); //3 //int randomValue = (int)((float)rand() / RAND_MAX * (n - 1)); //return (randomValue); } int main(){ int i, tab[100]; float ecart_type=0.0; srand(time(NULL)); //Initialise le tableau à 0: for(i=0;i<100;i++){ tab[i]=0; } //Rempli le tableau: for(i=0;i<2000000;i++){ tab[alea(100)]++; } //Calcul de l'écart-type: for(i=0;i<99;i++){ ecart_type=ecart_type+((tab[i]-tab[i+1])*(tab[i]-tab[i+1])); } ecart_type/=100; ecart_type=sqrt(ecart_type); printf("%f", ecart_type); return 0; }
Avec les deux premiers générateur de nombre aléatoire j'obtient un écart type d'environ 200 et avec la troisème solution, j'obtient un écart type d'environ 2000 !!!!!!

Est-ce normal ou alors il y a un problème dans mon programme ?

22/12/2005, 21h05
Jean-Marc.Bourguet

Citation:

Envoyé par casafa

Je vien de réaliser un programme qui me calcul la qualité d'un générateur de nombre aléatoire.

J'ai utilisé l'écart-type pour calculer la qualité du générateur de nombre aléatoire, est-ce une bonne idée ?

Il y a mieux, mais c'est pas trop mal comme premier indicateur. cad, un générateur qui ne passe pas ce test a de gros problèmes, mais passer ce test n'est en aucun cas un signe de qualité (la séquence 0, 1, 2, 3, 4, ... RAND_MAX aura un résultat aussi bon que possible!)

Code:

ecart_type=ecart_type+((tab[i]-tab[i+1])*(tab[i]-tab[i+1]));

Pourquoi compares-tu à l'échantillon après plutôt qu'à la moyenne?

Citation:

Avec les deux premiers générateur de nombre aléatoire j'obtient un écart type d'environ 200 et avec la troisème solution, j'obtient un écart type d'environ 2000 !!!!!!

J'avais pas remarqué un gros problème dans la méthode de la FAQ

Code:

int randomValue = (int)((float)rand() / RAND_MAX * (N - 1));

elle ne génère N-1 que quand rand() vaut RAND_MAX, càd pas très souvent. Ta mesure le mets très bien en évidence.

Puis-je te demander pourquoi tu n'as pas utilisé aussi l'autre méthode que je te proposais? Note que si ton générateur n'est pas trop mauvais et a un RAND_MAX assez grand, il est fort probable que calculer l'écart type ne te permette pas de départager les différentes méthodes.
22/12/2005, 22h36
casafa

-Je testé ton algo mais je ne l'ait pas mis dans mon code histoire de ne pas avoir 36 000 lignes de code sur le forum.
Pour info: ton code à aussi un écart type d'environ 200...

-Mon RAND_MAX est de 2^15 et en effet il est plutot très difficile de départager ton code ainsi que les 2 premier de mon programme.
Comment faire un programme qui permettrait de les départager ?
J'ai esseyer de diminuer RAND_MAX dans stdlib.h mais après ça mon programme n'arretait pas de planter :(

-"Pourquoi compares-tu à l'échantillon après plutôt qu'à la moyenne?" ==> je ne comprend pas bien ta question...(je ne suis pas dutout une bête des maths, lol) : j'ai juste fait le calcul necessaire pour avoir l'écart type.

Bien vue pour l'erreur dans la FAQ ;) , il va falloir changer ça !
22/12/2005, 23h25
Jean-Marc.Bourguet
Citation:

Envoyé par casafa

Mon RAND_MAX est de 2^15

Bizarre, je me serait attendu a INT_MAX ou bien a 2^15-1. Tu es sûr que ce n'est pas 2^15-1?

Citation:

et en effet il est plutot très difficile de départager ton code ainsi que les 2 premier de mon programme.
Comment faire un programme qui permettrait de les départager ?
J'ai esseyer de diminuer RAND_MAX dans stdlib.h mais après ça mon programme n'arretait pas de planter :(

Si RAND_MAX est 2^15-1, tu peux utiliser
Code:

1 2 3 4 #define MY_RAND_MAX 127 int my_rand() { return rand() % (MY_RAND_MAX+1); }
a la place de rand() et normalement mon code sera nettement meilleur que les autres :-) En gardant MY_RAND_MAX a un de moins que des puissance de deux tout en l'augmentant, tu devrais remarquer une convergence des ecart-types (en fait celui pour ma méthode ne devrait pas varier, les autres bien).

Citation:

-"Pourquoi compares-tu à l'échantillon après plutôt qu'à la moyenne?" ==> je ne comprend pas bien ta question...(je ne suis pas dutout une bête des maths, lol) : j'ai juste fait le calcul necessaire pour avoir l'écart type.

Moi je l'aurais calculé par
Code:

1 2 3 4 5 for(i=0;i<100;i++){ ecart_type=ecart_type+((tab[i]-20000)*(tab[i]-20000)); } ecart_type/=100; ecart_type=sqrt(ecart_type);

Re: Nombres aléatoires.

Citation:

Envoyé par Jean-Marc.Bourguet

Citation:

Envoyé par HanLee

[Ah j'suis content :), quelqu'un qui explique ce problème et résoud simplement (avec le do-while) comme moi j'l'ai fait, ya 2 ans, mais personne ne voulait m'écouter :/.

Ca me semble etre la methode classique des gens qui comprennent le probleme ;-)

Citation:

Et donc ainsi, on fait la méthode du modulo parce qu'on sait que les nombres que l'on tire ont meme probabilité de sortir car on a filtré les indésirables.

Et donc tu as le probleme que tu utilises les bits de poids faibles qui sont trop souvent de moins bonne qualite que les bits de poids forts. C'est pour cela que je refais une division plutot qu'un modulo.

Ah, peut-être.
En tout cas j'avais fait des statistiques pour un dé à 12 faces, avec 10 000 000 tirages. On obtenait ces probabilités :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 ' 1' : 0.083405 ' 2' : 0.0832778 ' 3' : 0.0833042 ' 4' : 0.0834181 ' 5' : 0.0832634 ' 6' : 0.0834367 ' 7' : 0.083342 ' 8' : 0.0832347 ' 9' : 0.0833318 '10' : 0.0832765 '11' : 0.0833496 '12' : 0.0833602

22/12/2005, 23h38
casafa

Oui c'est bien (2^15)-1.
Merci, je testerai tout ça demain :)
23/12/2005, 10h58
Jean-Marc.Bourguet

Re: Nombres aléatoires.

Citation:

Envoyé par HanLee

Citation:

Envoyé par Jean-Marc.Bourguet

Et donc tu as le probleme que tu utilises les bits de poids faibles qui sont trop souvent de moins bonne qualite que les bits de poids forts. C'est pour cela que je refais une division plutot qu'un modulo.

Ah, peut-être.
En tout cas j'avais fait des statistiques pour un dé à 12 faces, avec 10 000 000 tirages. On obtenait ces probabilités :

J'ai pas envie d'aller chercher les infos nécessaires pour voir si ce que tu optiens a un biais ou pas. Surtout qu'il y a des problèmes qui ne serait pas détectés: par exemple si ton générateur alterne les nombres pairs et les nombres impairs, tu peux optenir ces résultats. Il n'empèche que le dernier bit serait bien peu aléatoire.

RE-EDIT:
Je vien de re-refaire mon programme et j'ai obtenu ce résultat:
-J'ai un écart type d'environ 30 pour les solutions avec le modulo et la division.
-J'ai un écart-type d'environ 9 pour la solution avec le do/while.

Voici le programme pour ceux que ça interresse:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <assert.h>
 
int alea(int n){
//1
	//int randomValue = (int)((double)rand() / (RAND_MAX+1) * n);
	//return (randomValue);
 
//2
	//return (rand()%n);
 
//3
/*
   assert (0 < n && n-1 <= RAND_MAX);
   int partSize = 1 + (RAND_MAX - (n-1)) / n;
   int maxUsefull = partSize * n;
   int draw;
   do {
      draw = rand();
   } while (draw >= maxUsefull);
   return draw/partSize; 
  */
}
 
int main(){
	int i, tab[24000];
	float ecart_type=0.0;
	srand(time(NULL));
 
	//Initialise le tableau à 0:
	for(i=0;i<24000;i++){
		tab[i]=0;
	}
 
	//Rempli le tableau:
	for(i=0;i<2000000;i++){
		tab[alea(24000)]++;	
	}
 
	//Calcul de l'écart-type:
	for(i=0;i<24000;i++){
		ecart_type=ecart_type+((tab[i]-83)*(tab[i]-83));
	}
	ecart_type/=24000;
	ecart_type=sqrt(ecart_type);
	printf("%f", ecart_type);
 
	return 0;
}

J'ai du mal à comprendre ce script:
Code:

1 2 3 4 5 6 7 8 9 10 11 int alea(int n) { assert (0 < n && n-1 <= RAND_MAX); int partSize = 1 + (RAND_MAX - (n-1)) / n; int maxUsefull = partSize * n; int draw; do { draw = rand(); } while (draw >= maxUsefull); return draw/partSize; }
Il me semble qu'au lieu d'écrire ça:
Code:

1 2 int partSize = 1 + (RAND_MAX - (n-1)) / n; int maxUsefull = partSize * n;
on pourrai écrire ça (ça donne exactement le même résultat):
Code:

1 2 int partSize = 1 + (RAND_MAX - (n-1)) / n; int maxUsefull = RAND_MAX+1;
Donc il me semble que la condition de la boucle do/while sera toujours TRUE !

Dans un de tes message tu dit que la complication du calcul de partSize, c'est au cas où RAND_MAX serait égal à INT_MAX. Que vaut INT_MAX ? sizeof(int) ???

23/12/2005, 15h24
fearyourself

Citation:

on pourrai écrire ça (ça donne exactement le même résultat):

Ce n'est pas vrai, la division entière fait qu'on ne tombe pas sur le même nombre...

Exemple:

(5/2) * 2 -> 2 * 2 -> 2

Citation:
Envoyé par casafa
J'ai du mal à comprendre ce script:
Code:

1 2 3 4 5 6 7 8 9 10 11 int alea(int n) { assert (0 < n && n-1 <= RAND_MAX); int partSize = 1 + (RAND_MAX - (n-1)) / n; int maxUsefull = partSize * n; int draw; do { draw = rand(); } while (draw >= maxUsefull); return draw/partSize; }
Il me semble qu'au lieu d'écrire ça:
Code:

1 2 int partSize = 1 + (RAND_MAX - (n-1)) / n; int maxUsefull = partSize * n;
on pourrai écrire ça (ça donne exactement le même résultat):
Code:

1 2 int partSize = 1 + (RAND_MAX - (n-1)) / n; int maxUsefull = RAND_MAX+1;
Ce serait vrai si partSize était un nombre réel (et je n'ai pas écrit flottant). Mais c'est un entier.

Citation:

Donc il me semble que la condition de la boucle do/while sera toujours TRUE !

Tu veux dire FALSE je suppose.

Citation:

Dans un de tes message tu dit que la complication du calcul de partSize, c'est au cas où RAND_MAX serait égal à INT_MAX. Que vaut INT_MAX ? sizeof(int) ???

Tu fais bien de reparler de cela, il y a encore un problème dans le code que j'ai donné. Mais bon, INT_MAX est l'entier le plus grand représentable. sizeof(int) est la taille en byte d'un entier. Il y a une relation entre les deux (généralement INT_MAX vaut 2**(CHAR_BIT*sizeof int -1) -1) mais elle n'est pas si simple que ça.

Reprenons le problème que tu m'a fais remarquer: si RAND_MAX vaut INT_MAX et que n est un diviseur de RAND_MAX+1, maxUseFull vaut RAND_MAX+1 donc INT_MAX+1 qui n'est pas représentable. Corrigeons donc ma fonction:
Code:

1 2 3 4 5 6 7 8 9 10 11 int alea(int n) { assert (0 < n && n-1 <= RAND_MAX); int partSize = 1 + (RAND_MAX - (n-1)) / n; int maxUsefull = partSize * (n-1) + (n-1); int draw; do { draw = rand(); } while (draw > maxUsefull); return draw/partSize; }

Voir 40 message(s) de cette discussion en une page