Discussion :

[casafa]

J'ai enfin compris le principe de l'algo....mais il me reste 2 questions:

1) Je ne voi pas où il pourrait y avoir une erreur dans ce code même si INT_MAX=RAND_MAX:

Code :

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

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

2) Comment sont calculer RAND_MAX et INT_MAX ? Y a-til beaucoup de compilateur où INT_MAX=RAND_MAX ?

[Jean-Marc.Bourguet]

1) Je ne voi pas où il pourrait y avoir une erreur dans ce code même si INT_MAX=RAND_MAX:

Code :

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

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

Il n'y a plus de risque de dépassement de capacité des entiers. Son "problème" est que partSize est plus petit qu'autorisé quand n divise RAND_MAX+1 donc on va boucler plus souvent que nécessaire. Le pire cas est quand n vaut (RAND_MAX+1), tu vas boucler indéfiniment alors que le résultat de rand() est utilisable.

Note que ce pire cas montre à nouveau un problème aux limites, cette fois-ci dans l'interface de la fonction: on ne peut pas lui faire générer tous les entiers, même si RAND_MAX = INT_MAX. Corrigeons donc en lui faisant prendre le plus grand nombre générable:

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 <= RAND_MAX);
   int partSize = (RAND_MAX + 1U) / ((unsigned)n+1);
   int maxUsefull = partSize * n + (partSize-1);
   int draw;
   do {
      draw = rand();
   } while (draw > maxUsefull);
   return draw/partSize;
}

et notons qu'il faut passer par les unsigned pour être sûr de certains calculs mais que ça a simplifié l'expression (n vaut au moins 1 donc partSize peut être un int).

2) Comment sont calculer RAND_MAX et INT_MAX ?

Ils ne sont pas calculés, mais ce sont des constantes. INT_MAX est une caractéristique de l'architecture (p.e. les entiers sont représentés sur 32 bits en complément à 2 sans bits de padding ou de tag, ça implique que INT_MAX vaut 2^31-1). RAND_MAX est une caractéristique de la bibliothèque et plus précisément du générateur choisi.

Y a-til beaucoup de compilateur où INT_MAX=RAND_MAX ?

C'est le cas au moins pour Linux.

[casafa]

Tout d'abord : merci pour toutes tes réponses.

Alors la, j'ai rien compris...je comprend que ça boucle indéfiniment quand n = RAND_MAX+1 et il suffit de changer la condition dans assert pour éviter ce problème.
Mais pour tout le reste de l'explication de ton programme, je ne comprend pas.

1)Que signifie 1U en C ?
2)Je ne comprend vraiment pas c'est cette phrase: "Son problème est que partSize est plus petit qu'autorisé quand n divise RAND_MAX+1 donc on va boucler plus souvent que nécessaire. "
->Dans mon programme n divise RAND_MAX et non RAND_MAX+1 !

[Emmanuel Delahaye]

1)Que signifie 1U en C ?

Définit une expresion constante de type unsigned int valant 1.

[Jean-Marc.Bourguet]

Alors la, j'ai rien compris...je comprend que ça boucle indéfiniment quand n = RAND_MAX+1 et il suffit de changer la condition dans assert pour éviter ce problème.

Et donc refuser des gérer des cas sans bonnes raisons.

1)Que signifie 1U en C ?

Constante non signée. Comme ça je sais qu'il n'y a pas de problème de dépassement dans le calcul (RAND_MAX + 1U) / ((unsigned)n+1).

2)Je ne comprend vraiment pas c'est cette phrase: "Son problème est que partSize est plus petit qu'autorisé quand n divise RAND_MAX+1 donc on va boucler plus souvent que nécessaire. "
->Dans mon programme n divise RAND_MAX et non RAND_MAX+1 !

Par "n divise RAND_MAX+1" j'entendais "n est un diviseur de RAND_MAX+1".

[casafa]

Encore moi et mes questions de débutant...

1) int partSize = (RAND_MAX + 1U) / ((unsigned)n+1); ==> Il me semble qu'il y a un problème:
Imaginons que RAND_MAX soit égal à 9 et que n=5. PartSize vaudra [(9+1)/(5+1)]=1 alors qu'il pourrait très bien valloir 2 pour que la boucle tourne moins de fois, non ?

Donc ne vaudrait t-il pas mieux faire: int partSize = (RAND_MAX+1)/n; ?

2) Pour éviter tout problème quand RAND_MAX=INT_MAX, il suffit de déclarer les variables du script en "int unsigned", non ?

[Jean-Marc.Bourguet]

Encore moi et mes questions de débutant...

1) int partSize = (RAND_MAX + 1U) / ((unsigned)n+1); ==> Il me semble qu'il y a un problème:
Imaginons que RAND_MAX soit égal à 9 et que n=5. PartSize vaudra [(9+1)/(5+1)]=1 alors qu'il pourrait très bien valloir 2 pour que la boucle tourne moins de fois, non ?

Si c'était pas clair, j'ai changé l'interface: donc n dans cette version doit pouvoir être généré. Donc il y a n+1 valeurs à générer (à cause du 0), on est capable d'en généré RAND_MAX+1, donc il faut regrouper (RAND_MAX+1)/(n+1) valeurs retournées par rand() pour chaque valeur à générer.

2) Pour éviter tout problème quand RAND_MAX=INT_MAX, il suffit de déclarer les variables du script en "int unsigned", non ?

Il me semble que ça le ferait. Mais je n'aime pas mélanger les unsigned avec les signed -- c'est parfois surprenant -- et rand() retourne un signed...

[casafa]

Je comprend mieux maintenant mais j'ai un truc assez bizzard:

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
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <assert.h>
 
int alea(int unsigned n){
   assert (0 < n && n <= RAND_MAX);
   int partSize = (RAND_MAX+1U)/((unsigned)n+1);
   int maxUsefull = partSize * n + (partSize-1);
   int draw;
   do {
      draw = rand();
   } while (draw > maxUsefull);
   return draw/partSize; 
}
 
int main(){
	int i;
	srand(time(NULL));
	for(i=0;i<20;i++)
	  printf("%d\n", alea(5));
 
	return 0;
}

A chaque fois que j'exécute ce programme, le premier nombre afficher à l'écran n'est pas aléatoire: il vaut toujours 2 alors que les 19 autres nombres sont parfaitement aléatoire, pourquoi ?

[Jean-Marc.Bourguet]

Je comprend mieux maintenant mais j'ai un truc assez bizzard:

A chaque fois que j'exécute ce programme, le premier nombre afficher à l'écran n'est pas aléatoire: il vaut toujours 2 alors que les 19 autres nombres sont parfaitement aléatoire, pourquoi ?

Je n'observe pas ce comportement...

time() a une résolution d'une seconde. Il est donc assez facile de lancer le programme deux fois de suite dans la même seconde, mais dans ce cas les autres nombres sont semblables aussi.

[casafa]

Après quelque test j'ai remarqué ceci:

-Sur Windows avec MinGw/gcc 3.4.4, le premier nombre n'est pas aléatoire.
-Sur Linux je n'ait pas ce problème !

Donc je supose que c'est un problème avec Gcc sur Windows.

Pour finir: Merci à toi Jean-Marc Bourguet et à tous ceux qui ont participé à ce post et bonne fête à tous

[Emmanuel Delahaye]

A chaque fois que j'exécute ce programme, le premier nombre afficher à l'écran n'est pas aléatoire: il vaut toujours 2 alors que les 19 autres nombres sont parfaitement aléatoire, pourquoi ?

Je n'observe pas ce comportement...

Ce problème a été maintes fois signalé avec mingw (portage de gcc sous Windows).