rand() modulo, pourquoi pas ?

**JulienDuSud** · 27/10/2009, 12h44

Salut !

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

Code :

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

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 :

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

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 ?

**Chatanga** · 27/10/2009, 13h43

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

Code :

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

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.

**diogene** · 27/10/2009, 14h10

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.