rand() modulo, pourquoi pas ?

Salut !

Je viens de penser un truc.
Pour être honnête, je trouve le code dans la FAQ assez lourd

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

#include <stdlib.h>   int rand_n(int n) { int partSize = 1 + (n == RAND_MAX ? 0 : (RAND_MAX - n) / (n + 1)); int maxUsefull = partSize * n + (partSize - 1); int draw;   do { draw = rand(); } while (draw > maxUsefull);   return draw / partSize; }

---

Y a 3 variables, une boucle, bref bien trop lourd imo.

Pourquoi ne pas simplement utiliser quelque chose de ce style ?:

Code:

---

int n = (rand() >> 8) % x;

---

Cela permettrait d'éviter d'avantager les bits de poids le plus faible et me paraît plus performant en même temps.

Qu'en pensez-vous ?

Je pars du principe que tu as voulu écrire ceci :

Code:

---

1 2 3 4 5

int rand_n(int n) { return (rand() >> 8) % n; }

---

Soit N = (RAND_MAX >> 8) :

• si n > N, tu as un problème évident ;
• si n n'est pas divisible par N, tu n'aura pas une distribution uniforme des résultats.

Deux problèmes dont la version de la FAQ ne souffre pas.

Ce sera sans doute néfaste : pour corriger une éventuelle imperfection du générateur sur les bits de poids faible, on va augmenter le biais lié à l'utilisation du modulo.

Supposons ici le générateur de nombres pseudo-aléatoire parfait et qu'il délivre un nombre N , 0<= N <A, de façon équiprobable.

Alors v = N%n n'est pas ,en général, équiprobable entre 0 et n-1 :
En posant (division euclidienne) A = Qn+R avec 0<= R <n, les valeurs v obtenues lorsque N varie de 0 à A-1 sont en nombre de Q+1 pour 0<= v <R et de Q pour R<= v <n.
La probabilité d'obtenir 0<= v <R est de (Q+1)/A et pour R<= v <n de Q/A. L'écart de probabilité est d'autant plus faible que Q est grand, donc A grand devant n.

Continuons avec, pour simplifier mais je pense que c'est le cas le plus répandu, pour A une puissance de 2 : A = 2^P

Avec N' = N >> m , soit N' = N/2^m, on obtient des valeurs N' équiprobables avec 0 <= N' < A' où A' = 2^(P-m)
On est ramené au cas précédent avec A' plus petit que A

Par exemple :

- avec A = 32768 et n = 10, on a Q = 3276 et R = 8 .
La probabilité d'obtenir une valeur de 0 à 7 est de 3277/32768 = 0.10006 et pour 8 ou 9 de 3276/32768 = 0.099976

- Le même avec m=8 , N' = N>>8. On a A' = 128 , Q = 12 et R = 8.
La probabilité d'obtenir une valeur de 0 à 7 est de 13/128 = 0.1016 et pour 8 ou 9 de 12/128 = 0.0938.

Merci pour ces explications très précises :)

D'ailleurs j'y ai pensé durant ma sieste :D

Voir aussi cette discussion, qui peut t'éclairer un peu sur le sujet.