Version imprimable
Salut!
J'ai vu dans la FAQ C:
http://c.developpez.com/faq/c/?page=..._random_bornes
que rand%N n'était pas équiprobable et qu'il fallait préferer:
Pourquoi?Code:(int)((float)rand() / RAND_MAX * (N - 1));
La partie aléatoire n'est que dans "rand()" les autres opérations,une fois que "rand()" est fixé n'ont rien d'aléatoire.
Pourriez vous m'éclairer?
Merci! :D
Quelques explications dans ce thread : http://www.developpez.net/forums/vie...atoire#2464639
Si rand() tire un nombre entre 0 et 6 inclus de manière uniforme et que tu fais rand() % N, tu as une chance sur 4 d'avoir 0 et 1 sur 3 d'avoir 1. Ce n'est pas équiprobable.
par exemple si N=10:Citation:
Envoyé par Miles
on aura jamais 7,8,9!
Je commence à voir pourquoi ça ne marche pas sans pour autant cerner entierement le probleme.
Je vais consulter l'autre topic.
Merci! :D
Euh si, quand même.Citation:
par exemple si N=10:
on aura jamais 7,8,9!
Tous les cas ne sont pas précisément équiprobables. On n'y peut pas forcément grand chose. Par contre, cela s'agrave un petit peu si tu considères la probabibilité que ton résultat soit inférieur à un certan seuil.
Avec u_N uniforme sur [0..N[, amuses-toi à calculer formellement les réparttion de "u_N % K", et les probas de "u_N % k < S". Avec des valeurs petites les écarts introduits se voient mieux.
Après, remplace le modulo par une "remise à l'échelle" et refais les calculs.
Euh... non. Si rand() retourne un nombre entre 0 et 6, il n'y a aucune chance pour qu'il retourne 7, 8 ou 9.Citation:
Envoyé par loufoque
Note que la remise a l'echelle dans la FAQ est mal faite et ne fait que changer les nombres qui sont choisis plus souvent que les autres. Mais bon, je crois que j'expliquais ca dans l'autre thread.Citation:
Envoyé par Luc Hermitte
Le problème d'équiprobabilité ne vient pas vraiment de là. Les nombres générés sont assez grands pour éviter ce problème. Même si on considère des octets générés aléatoirement, et un modulo 6, on a des proba 42/256 et 43/256. En pratique c'est suffisemment proche.
Le gros problème est que lors que le générateur sort un nombre "aléatoire", tout les bits ne sont pas équivalent. Pour les générateurs les plus connus, les bits de poid fort sont assez bien répartis, ceux de poid faible ont une structure assez prévisible.
Il est par exemple possible que le bit 0 soit toujours nul. Dans ce cas un rand()%2 donnera toujours 0, alors qu'un rand()/2.0 aura le comportement souhaité.
C'est pour la même raison qu'on déconseille vivement de tirer plusieurs bits aléatoire d'un seul tirage. Si on a besoin de 4 bits, on fait 4 fois rand()/2.0, et pas un truc du genre rand() >> 12.
Merci de toutes vos explications! :applo:
J'y vois beaucoup plus clair.
Je met le tag :resolu:
La, il faut connaitre l'application pour se prononcer.Citation:
Envoyé par Ulmo
Tu as des references? Parce que ma comprehension etait pour le moins differente: un certain type de generateur a ce probleme pour de mauvais parametres. Un generateur de ce type etait donne en exemple dans la norme C avec de mauvais parametres mais a ete repris tel quel par certaines implementations. Une fois je me suis amuse a verifier, aucunes implementations que j'ai regardees n'utilisait ce generateur.Citation:
Le gros problème est que lors que le générateur sort un nombre "aléatoire", tout les bits ne sont pas équivalent. Pour les générateurs les plus connus, les bits de poid fort sont assez bien répartis, ceux de poid faible ont une structure assez prévisible.
Il parlait du code rand() % N.Citation:
Envoyé par Miles
Si N vaut 10, comme il le dit, alors on peut effectivement avoir 7, 8 ou 9.
Tu lis seulement la moitié des messages ?