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...

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).

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.

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.

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.

Envoyé par Jean-Marc.Bourguet

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 :

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

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 :

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

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);
}

Bonjour,

Envoyé par Jean-Marc.Bourguet

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

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 :

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

-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 !

Envoyé par Jean-Marc.Bourguet

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 ;-)

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 :

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

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

Oui c'est bien (2^15)-1.
Merci, je testerai tout ça demain

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 :

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

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

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 :

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

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 :

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

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