J'ai vu cette question beaucoup posée mais je n'ai jamais vu de vraie réponse concrète. Je vais donc en poster un ici qui, espérons-le, aidera les gens à comprendre pourquoi il existe exactement un "biais modulo" lors de l'utilisation d'un générateur de nombres aléatoires, comme rand()en C ++.

Il en rand()va de même d'un générateur de nombres pseudo-aléatoires qui choisit un nombre naturel entre 0 et RAND_MAX, qui est une constante définie dans cstdlib(voir cet article pour un aperçu général rand()).

Maintenant, que se passe-t-il si vous voulez générer un nombre aléatoire entre disons 0 et 2? Pour des raisons d'explication, disons RAND_MAXest 10 et je décide de générer un nombre aléatoire entre 0 et 2 en appelant rand()%3. Cependant, rand()%3ne produit pas les nombres entre 0 et 2 avec une probabilité égale!

Lorsque rand()renvoie 0, 3, 6 ou 9 rand()%3 == 0 ,. Par conséquent, P (0) = 4/11

Lorsque rand()renvoie 1, 4, 7 ou 10 rand()%3 == 1 ,. Par conséquent, P (1) = 4/11

Lorsque rand()renvoie 2, 5 ou 8 rand()%3 == 2 ,. Par conséquent, P (2) = 3/11

Cela ne génère pas les nombres entre 0 et 2 avec une probabilité égale. Bien sûr, pour les petites plages, ce n'est peut-être pas le plus gros problème, mais pour une plus grande plage, cela pourrait fausser la distribution, biaisant les petits nombres.

Alors, quand rand()%nrenvoie une plage de nombres de 0 à n-1 avec une probabilité égale? Quand RAND_MAX%n == n - 1. Dans ce cas, avec notre hypothèse précédente, rand()renvoie un nombre compris entre 0 et RAND_MAXavec une probabilité égale, les classes modulo de n seraient également réparties également.

Alors, comment pouvons-nous résoudre ce problème? Une façon grossière est de continuer à générer des nombres aléatoires jusqu'à ce que vous obteniez un nombre dans la plage souhaitée:

int x; 
do {
    x = rand();
} while (x >= n);

mais cela est inefficace pour les valeurs faibles de n, car vous n'avez qu'une n/RAND_MAXchance d'obtenir une valeur dans votre plage, et vous devrez donc effectuer des RAND_MAX/nappels vers rand()en moyenne.

Une approche de formule plus efficace consisterait à prendre une grande plage avec une longueur divisible par n, comme RAND_MAX - RAND_MAX % n, continuer à générer des nombres aléatoires jusqu'à ce que vous obteniez celui qui se trouve dans la plage, puis à prendre le module:

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

Pour les petites valeurs de n, cela nécessitera rarement plus d'un appel à rand().

Ouvrages cités et lectures complémentaires:

• Référence CPlusPlus

• Éternellement confus

Continuer à sélectionner un hasard est un bon moyen de supprimer le biais.

Mettre à jour

Nous pourrions rendre le code rapide si nous recherchons un x dans la plage divisible par n.

// Assumptions
// rand() in [0, RAND_MAX]
// n in (0, RAND_MAX]

int x; 

// Keep searching for an x in a range divisible by n 
do {
    x = rand();
} while (x >= RAND_MAX - (RAND_MAX % n)) 

x %= n;

La boucle ci-dessus devrait être très rapide, disons 1 itération en moyenne.

@ user1413793 a raison du problème. Je ne vais pas en parler davantage, sauf pour faire une remarque: oui, pour les petites valeurs de net les grandes valeurs de RAND_MAX, le biais modulo peut être très petit. Mais l'utilisation d'un modèle induisant un biais signifie que vous devez tenir compte du biais chaque fois que vous calculez un nombre aléatoire et choisir des modèles différents pour différents cas. Et si vous faites le mauvais choix, les bugs qu'il introduit sont subtils et presque impossibles à tester unitairement. Comparé à l'utilisation de l'outil approprié (tel que arc4random_uniform), c'est un travail supplémentaire, pas moins de travail. Faire plus de travail et obtenir une pire solution est une ingénierie terrible, surtout quand il est facile de bien le faire à chaque fois sur la plupart des plates-formes.

Malheureusement, les implémentations de la solution sont toutes incorrectes ou moins efficaces qu'elles ne devraient l'être. (Chaque solution a divers commentaires expliquant les problèmes, mais aucune des solutions n'a été corrigée pour les résoudre.) Cela est susceptible de dérouter le chercheur de réponse occasionnel, donc je fournis ici une bonne mise en œuvre connue.

Encore une fois, la meilleure solution est simplement d'utiliser arc4random_uniformsur les plates-formes qui le fournissent, ou une solution à distance similaire pour votre plate-forme (comme Random.nextIntsur Java). Il fera la bonne chose sans aucun coût pour vous. C'est presque toujours l'appel correct à faire.

Si ce n'est pas le cas arc4random_uniform, vous pouvez utiliser la puissance de l'opensource pour voir exactement comment il est implémenté au-dessus d'un RNG à plus large éventail ( ar4randomdans ce cas, mais une approche similaire pourrait également fonctionner au-dessus d'autres RNG).

Voici l' implémentation d'OpenBSD :

/*
 * Calculate a uniformly distributed random number less than upper_bound
 * avoiding "modulo bias".
 *
 * Uniformity is achieved by generating new random numbers until the one
 * returned is outside the range [0, 2**32 % upper_bound).  This
 * guarantees the selected random number will be inside
 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 * after reduction modulo upper_bound.
 */
u_int32_t
arc4random_uniform(u_int32_t upper_bound)
{
    u_int32_t r, min;

    if (upper_bound < 2)
        return 0;

    /* 2**32 % x == (2**32 - x) % x */
    min = -upper_bound % upper_bound;

    /*
     * This could theoretically loop forever but each retry has
     * p > 0.5 (worst case, usually far better) of selecting a
     * number inside the range we need, so it should rarely need
     * to re-roll.
     */
    for (;;) {
        r = arc4random();
        if (r >= min)
            break;
    }

    return r % upper_bound;
}

Il convient de noter le dernier commentaire de validation sur ce code pour ceux qui ont besoin d'implémenter des choses similaires:

Modifiez arc4random_uniform () pour calculer 2**32 % upper_boundcomme -upper_bound % upper_bound. Simplifie le code et le rend identique sur les architectures ILP32 et LP64, et également légèrement plus rapide sur les architectures LP64 en utilisant un reste 32 bits au lieu d'un reste 64 bits.

Souligné par Jorden Verwer sur tech @ ok deraadt; aucune objection de djm ou otto

L'implémentation Java est également facilement repérable (voir le lien précédent):

public int nextInt(int n) {
   if (n <= 0)
     throw new IllegalArgumentException("n must be positive");

   if ((n & -n) == n)  // i.e., n is a power of 2
     return (int)((n * (long)next(31)) >> 31);

   int bits, val;
   do {
       bits = next(31);
       val = bits % n;
   } while (bits - val + (n-1) < 0);
   return val;
 }

Définition

Modulo Bias biais modulo est le biais inhérent à l'utilisation de l'arithmétique modulo pour réduire un ensemble de sortie à un sous-ensemble de l'ensemble d'entrée. En général, un biais existe chaque fois que le mappage entre l'ensemble d'entrée et l'ensemble de sortie n'est pas également distribué, comme dans le cas de l'utilisation de l'arithmétique modulo lorsque la taille de l'ensemble de sortie n'est pas un diviseur de la taille de l'ensemble d'entrée.

Ce biais est particulièrement difficile à éviter en informatique, où les nombres sont représentés sous la forme de chaînes de bits: 0 et 1. Trouver des sources de hasard vraiment aléatoires est également extrêmement difficile, mais dépasse le cadre de cette discussion.Pour le reste de cette réponse, supposons qu'il existe une source illimitée de bits vraiment aléatoires.

Exemple de problème

Considérons la simulation d'un jet de dé (0 à 5) à l'aide de ces bits aléatoires. Il y a 6 possibilités, nous avons donc besoin de suffisamment de bits pour représenter le nombre 6, qui est de 3 bits. Malheureusement, 3 bits aléatoires donnent 8 résultats possibles:

000 = 0, 001 = 1, 010 = 2, 011 = 3
100 = 4, 101 = 5, 110 = 6, 111 = 7

Nous pouvons réduire la taille de l'ensemble de résultats à exactement 6 en prenant la valeur modulo 6, mais cela présente le problème de biais modulo : 110donne un 0 et 111donne un 1. Ce dé est chargé.

Solutions potentielles

Approche 0:

Plutôt que de compter sur des bits aléatoires, en théorie, on pourrait embaucher une petite armée pour lancer des dés toute la journée et enregistrer les résultats dans une base de données, puis utiliser chaque résultat une seule fois. C'est à peu près aussi pratique que cela puisse paraître, et plus que probable ne donnerait de toute façon pas de résultats vraiment aléatoires (jeu de mots).

Approche 1:

Au lieu d'utiliser le module, une solution naïve mais mathématiquement correcte consiste à rejeter les résultats qui donnent 110et à 111réessayer simplement avec 3 nouveaux bits. Malheureusement, cela signifie qu'il y a 25% de chances sur chaque lancer qu'un relancement sera nécessaire, y compris chacun des relances eux - mêmes. Ceci est clairement impraticable pour tous, mais le plus trivial des utilisations.

Approche 2:

Utilisez plus de bits: au lieu de 3 bits, utilisez 4. Cela donne 16 résultats possibles. Bien sûr, une relance à chaque fois que le résultat est supérieur à 5 aggrave les choses (10/16 = 62,5%) de sorte que cela ne suffira pas à lui seul.

Notez que 2 * 6 = 12 <16, afin que nous puissions prendre en toute sécurité tout résultat inférieur à 12 et réduire ce module 6 pour répartir uniformément les résultats. Les 4 autres résultats doivent être rejetés, puis relancés comme dans l'approche précédente.

Sonne bien au début, mais vérifions les calculs:

4 discarded results / 16 possibilities = 25%

Dans ce cas, 1 bit supplémentaire n'a pas aidé du tout!

Ce résultat est regrettable, mais réessayons avec 5 bits:

32 % 6 = 2 discarded results; and
2 discarded results / 32 possibilities = 6.25%

Une amélioration certaine, mais insuffisante dans de nombreux cas pratiques. La bonne nouvelle est que l' ajout de bits n'augmentera jamais les chances de devoir se défaire et relancer . Cela vaut non seulement pour les dés, mais dans tous les cas.

Comme démontré cependant, l'ajout d'un bit supplémentaire peut ne rien changer. En fait, si nous augmentons notre roulement à 6 bits, la probabilité reste de 6,25%.

Cela soulève 2 questions supplémentaires:

1. Si nous ajoutons suffisamment de bits, y a-t-il une garantie que la probabilité d'un rejet diminuera?
2. Combien de bits suffisent dans le cas général?

Solution générale

Heureusement, la réponse à la première question est oui. Le problème avec 6 est que 2 ^ x mod 6 bascule entre 2 et 4 qui sont par coïncidence un multiple de 2 les uns des autres, de sorte que pour un x pair> 1,

[2^x mod 6] / 2^x == [2^(x+1) mod 6] / 2^(x+1)

Ainsi, 6 est une exception plutôt que la règle. Il est possible de trouver des modules plus grands qui donnent des puissances consécutives de 2 de la même manière, mais finalement cela doit s'enrouler et la probabilité d'un rejet sera réduite.

Sans autre preuve, en général, l'utilisation du double du nombre de bits requis offrira une chance de rejet plus petite, généralement insignifiante.

Preuve de concept

Voici un exemple de programme qui utilise libcrypo d'OpenSSL pour fournir des octets aléatoires. Lors de la compilation, assurez-vous de créer un lien vers la bibliothèque avec -lcryptolaquelle tout le monde devrait avoir accès.

#include <iostream>
#include <assert.h>
#include <limits>
#include <openssl/rand.h>

volatile uint32_t dummy;
uint64_t discardCount;

uint32_t uniformRandomUint32(uint32_t upperBound)
{
    assert(RAND_status() == 1);
    uint64_t discard = (std::numeric_limits<uint64_t>::max() - upperBound) % upperBound;
    uint64_t randomPool = RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));

    while(randomPool > (std::numeric_limits<uint64_t>::max() - discard)) {
        RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));
        ++discardCount;
    }

    return randomPool % upperBound;
}

int main() {
    discardCount = 0;

    const uint32_t MODULUS = (1ul << 31)-1;
    const uint32_t ROLLS = 10000000;

    for(uint32_t i = 0; i < ROLLS; ++i) {
        dummy = uniformRandomUint32(MODULUS);
    }
    std::cout << "Discard count = " << discardCount << std::endl;
}

J'encourage à jouer avec les valeurs MODULUSet ROLLSpour voir combien de relances se produisent réellement dans la plupart des conditions. Une personne sceptique peut également souhaiter enregistrer les valeurs calculées dans un fichier et vérifier que la distribution semble normale.

Il y a deux plaintes habituelles avec l'utilisation de modulo.

• une est valable pour tous les générateurs. Il est plus facile de voir dans un cas limite. Si votre générateur a un RAND_MAX qui est 2 (qui n'est pas conforme à la norme C) et que vous ne voulez que 0 ou 1 comme valeur, l'utilisation de modulo générera 0 deux fois plus souvent (lorsque le générateur génère 0 et 2) comme il le fera générer 1 (lorsque le générateur génère 1). Notez que cela est vrai dès que vous ne supprimez pas de valeurs, quel que soit le mappage que vous utilisez des valeurs du générateur à la valeur souhaitée, l'une se produit deux fois plus souvent que l'autre.

• certains types de générateurs ont leurs bits moins significatifs moins aléatoires que les autres, au moins pour certains de leurs paramètres, mais malheureusement, ces paramètres ont d'autres caractéristiques intéressantes (comme le fait d'avoir RAND_MAX un de moins qu'une puissance de 2). Le problème est bien connu et depuis longtemps l'implémentation de la bibliothèque évite probablement le problème (par exemple, l'implémentation de rand () dans le standard C utilise ce type de générateur, mais laisse tomber les 16 bits les moins significatifs), mais certains aiment se plaindre et vous risquez de ne pas avoir de chance

Utiliser quelque chose comme

int alea(int n){ 
 assert (0 < n && n <= RAND_MAX); 
 int partSize = 
      n == RAND_MAX ? 1 : 1 + (RAND_MAX-n)/(n+1); 
 int maxUsefull = partSize * n + (partSize-1); 
 int draw; 
 do { 
   draw = rand(); 
 } while (draw > maxUsefull); 
 return draw/partSize; 
}

générer un nombre aléatoire entre 0 et n évitera les deux problèmes (et cela évite le débordement avec RAND_MAX == INT_MAX)

BTW, C ++ 11 a introduit des moyens standard pour la réduction et un autre générateur que rand ().

La solution de Mark (la solution acceptée) est presque parfaite.

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

édité le 25 mars 16 à 23:16

Mark Amery 39k21170211

Cependant, il a une mise en garde qui rejette 1 ensemble valide de résultats dans tout scénario où RAND_MAX( RM) est 1 de moins qu'un multiple de N(Où N= le nombre de résultats valides possibles).

c'est-à-dire, lorsque le «nombre de valeurs rejetées» ( D) est égal à N, alors il s'agit en fait d'un ensemble valide ( V), et non d'un ensemble non valide ( I).

Ce qui en est la cause à un moment donné, Mark perd de vue la différence entre Net Rand_Max.

Nest un ensemble dont les membres valides sont composés uniquement d'entiers positifs, car il contient un nombre de réponses qui seraient valides. (par exemple: Set N= {1, 2, 3, ... n })

Rand_max Cependant, il s'agit d'un ensemble qui (tel que défini pour nos besoins) comprend un nombre quelconque d'entiers non négatifs.

Dans sa forme la plus générique, ce qui est défini ici Rand Maxest l'ensemble de tous les résultats valides, qui pourrait théoriquement inclure des nombres négatifs ou des valeurs non numériques.

Par conséquent, Rand_Maxest mieux défini comme l'ensemble des «réponses possibles».

Cependant, il Nopère par rapport au nombre de valeurs dans l'ensemble des réponses valides, donc même tel que défini dans notre cas spécifique, il y Rand_Maxaura une valeur inférieure au nombre total qu'il contient.

En utilisant la solution de Mark, les valeurs sont rejetées lorsque: X => RM - RM% N

EG: 

Ran Max Value (RM) = 255
Valid Outcome (N) = 4

When X => 252, Discarded values for X are: 252, 253, 254, 255

So, if Random Value Selected (X) = {252, 253, 254, 255}

Number of discarded Values (I) = RM % N + 1 == N

 IE:

 I = RM % N + 1
 I = 255 % 4 + 1
 I = 3 + 1
 I = 4

   X => ( RM - RM % N )
 255 => (255 - 255 % 4) 
 255 => (255 - 3)
 255 => (252)

 Discard Returns $True

Comme vous pouvez le voir dans l'exemple ci-dessus, lorsque la valeur de X (le nombre aléatoire que nous obtenons de la fonction initiale) est 252, 253, 254 ou 255, nous la rejetons même si ces quatre valeurs comprennent un ensemble valide de valeurs renvoyées .

IE: lorsque le nombre de valeurs rejetées (I) = N (le nombre de résultats valides), un ensemble valide de valeurs de retour sera rejeté par la fonction d'origine.

Si nous décrivons la différence entre les valeurs N et RM comme D, c'est-à-dire:

D = (RM - N)

Puis, à mesure que la valeur de D diminue, le pourcentage de relances inutiles dues à cette méthode augmente à chaque multiplicatif naturel. (Lorsque RAND_MAX n'est PAS égal à un nombre premier, cela est une préoccupation valable)

PAR EXEMPLE:

RM=255 , N=2 Then: D = 253, Lost percentage = 0.78125%

RM=255 , N=4 Then: D = 251, Lost percentage = 1.5625%
RM=255 , N=8 Then: D = 247, Lost percentage = 3.125%
RM=255 , N=16 Then: D = 239, Lost percentage = 6.25%
RM=255 , N=32 Then: D = 223, Lost percentage = 12.5%
RM=255 , N=64 Then: D = 191, Lost percentage = 25%
RM=255 , N= 128 Then D = 127, Lost percentage = 50%

Étant donné que le pourcentage de relances nécessaires augmente à mesure que N se rapproche de RM, cela peut être une préoccupation valable pour de nombreuses valeurs différentes en fonction des contraintes du système exécutant le code et des valeurs recherchées.

Pour annuler cela, nous pouvons apporter un amendement simple, comme indiqué ici:

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

 x %= n;

Cela fournit une version plus générale de la formule qui tient compte des particularités supplémentaires de l'utilisation du module pour définir vos valeurs maximales.

Exemples d'utilisation d'une petite valeur pour RAND_MAX qui est un multiplicatif de N.

Version Mark'original:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X >= (RAND_MAX - ( RAND_MAX % n ) )
When X >= 2 the value will be discarded, even though the set is valid.

Version généralisée 1:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X > (RAND_MAX - ( ( RAND_MAX % n  ) + 1 ) % n )
When X > 3 the value would be discarded, but this is not a vlue in the set RAND_MAX so there will be no discard.

De plus, dans le cas où N doit être le nombre de valeurs dans RAND_MAX; dans ce cas, vous pouvez définir N = RAND_MAX +1, sauf si RAND_MAX = INT_MAX.

En boucle, vous pouvez simplement utiliser N = 1, et toute valeur de X sera acceptée, cependant, et mettez une instruction IF pour votre multiplicateur final. Mais vous avez peut-être du code qui peut avoir une raison valable de retourner un 1 lorsque la fonction est appelée avec n = 1 ...

Il peut donc être préférable d'utiliser 0, qui fournirait normalement une erreur Div 0, lorsque vous souhaitez avoir n = RAND_MAX + 1

Version généralisée 2:

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

    x %= n;
} else {
    x = rand();
}

Ces deux solutions résolvent le problème avec des résultats valides inutilement rejetés qui se produiront lorsque RM + 1 est un produit de n.

La deuxième version couvre également le scénario de cas de bord lorsque vous avez besoin de n pour égaler l'ensemble total possible de valeurs contenues dans RAND_MAX.

L'approche modifiée dans les deux est la même et permet une solution plus générale au besoin de fournir des nombres aléatoires valides et de minimiser les valeurs rejetées.

Recommencer:

La solution générale de base qui prolonge l'exemple de Mark:

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );

 x %= n;

La solution générale étendue qui permet un scénario supplémentaire de RAND_MAX + 1 = n:

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ) );

    x %= n;
} else {
    x = rand();
}

Dans certaines langues (en particulier les langues interprétées), le calcul de l'opération de comparaison en dehors de la condition while peut conduire à des résultats plus rapides car il s'agit d'un calcul unique, quel que soit le nombre de réessais requis. YMMV!

// Assumes:
//  RAND_MAX is a globally defined constant, returned from the environment.
//  int n; // User input, or externally defined, number of valid choices.

int x; // Resulting random number
int y; // One-time calculation of the compare value for x

if n != 0 {
    y = RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) 
    do {
        x = rand();
    } while (x > y);

    x %= n;
} else {
    x = rand();
}

Avec une RAND_MAXvaleur de 3(en réalité, elle devrait être beaucoup plus élevée que cela mais le biais existerait toujours), il est logique à partir de ces calculs qu'il existe un biais:

1 % 2 = 1 2 % 2 = 0 3 % 2 = 1 random_between(1, 3) % 2 = more likely a 1

Dans ce cas, % 2c'est ce que vous ne devez pas faire lorsque vous voulez un nombre aléatoire entre 0et 1. Vous pouvez cependant obtenir un nombre aléatoire entre 0et 2en faisant % 3, car dans ce cas: RAND_MAXest un multiple de 3.

Une autre méthode

Il y a beaucoup plus simple mais pour ajouter à d'autres réponses, voici ma solution pour obtenir un nombre aléatoire entre 0et n - 1, donc ndifférentes possibilités, sans biais.

• le nombre de bits (pas d'octets) nécessaires pour encoder le nombre de possibilités est le nombre de bits de données aléatoires dont vous aurez besoin
• encoder le nombre à partir de bits aléatoires
• si ce nombre est >= n, redémarrez (pas de module).

Les données vraiment aléatoires ne sont pas faciles à obtenir, alors pourquoi utiliser plus de bits que nécessaire.

Voici un exemple dans Smalltalk, utilisant un cache de bits provenant d'un générateur de nombres pseudo-aléatoires. Je ne suis pas un expert en sécurité, alors utilisez-le à vos risques et périls.

next: n

    | bitSize r from to |
    n < 0 ifTrue: [^0 - (self next: 0 - n)].
    n = 0 ifTrue: [^nil].
    n = 1 ifTrue: [^0].
    cache isNil ifTrue: [cache := OrderedCollection new].
    cache size < (self randmax highBit) ifTrue: [
        Security.DSSRandom default next asByteArray do: [ :byte |
            (1 to: 8) do: [ :i |    cache add: (byte bitAt: i)]
        ]
    ].
    r := 0.
    bitSize := n highBit.
    to := cache size.
    from := to - bitSize + 1.
    (from to: to) do: [ :i |
        r := r bitAt: i - from + 1 put: (cache at: i)
    ].
    cache removeFrom: from to: to.
    r >= n ifTrue: [^self next: n].
    ^r

Comme l' indique la réponse acceptée , le "biais modulo" a ses racines dans la faible valeur de RAND_MAX. Il utilise une valeur extrêmement petite de RAND_MAX(10) pour montrer que si RAND_MAX était 10, alors vous avez essayé de générer un nombre compris entre 0 et 2 en utilisant%, les résultats suivants en résulteraient:

rand() % 3   // if RAND_MAX were only 10, gives
output of rand()   |   rand()%3
0                  |   0
1                  |   1
2                  |   2
3                  |   0
4                  |   1
5                  |   2
6                  |   0
7                  |   1
8                  |   2
9                  |   0

Il y a donc 4 sorties de 0 (4/10 chances) et seulement 3 sorties de 1 et 2 (3/10 chances chacune).

C'est donc biaisé. Les nombres inférieurs ont de meilleures chances de sortir.

Mais cela n'apparaît que si évidemment quand il RAND_MAXest petit . Ou plus précisément, lorsque le nombre par lequel vous modifiez est important par rapport àRAND_MAX.

Une bien meilleure solution que le bouclage (ce qui est incroyablement inefficace et ne devrait même pas être suggéré) consiste à utiliser un PRNG avec une plage de sortie beaucoup plus grande. L' algorithme Mersenne Twister a une sortie maximale de 4 294 967 295. En tant que tel, faire MersenneTwister::genrand_int32() % 10à toutes fins utiles sera réparti également et l'effet de biais modulo disparaîtra pratiquement.

Je viens d'écrire un code pour la méthode de retournement de pièces non biaisé de Von Neumann, qui devrait théoriquement éliminer tout biais dans le processus de génération de nombres aléatoires. Plus d'informations peuvent être trouvées sur ( http://en.wikipedia.org/wiki/Fair_coin )

int unbiased_random_bit() {    
    int x1, x2, prev;
    prev = 2;
    x1 = rand() % 2;
    x2 = rand() % 2;

    for (;; x1 = rand() % 2, x2 = rand() % 2)
    {
        if (x1 ^ x2)      // 01 -> 1, or 10 -> 0.
        {
            return x2;        
        }
        else if (x1 & x2)
        {
            if (!prev)    // 0011
                return 1;
            else
                prev = 1; // 1111 -> continue, bias unresolved
        }
        else
        {
            if (prev == 1)// 1100
                return 0;
            else          // 0000 -> continue, bias unresolved
                prev = 0;
        }
    }
}