Uniformité des nombres aléatoires pris modulo N

Une méthode courante pour choisir un nombre aléatoire dans [0, n) consiste à prendre le résultat de rand() modulo n : rand() % n . Cependant, même si les résultats renvoyés par l’implémentation disponible de rand() sont parfaitement uniformes, l’uniformité des nombres [0, n) ainsi RAND_MAX + 1 ne devrait-elle pas poser problème lorsque RAND_MAX + 1 ne se divise pas également par n ? Par exemple, supposons que RAND_MAX soit RAND_MAX 2 et n RAND_MAX 2. Ensuite, sur 3 sorties rand() possibles: 0, 1 et 2, nous obtenons respectivement 0, 1 et 0 lorsque nous les utilisons modulo n . Par conséquent, la sortie ne sera pas uniforme du tout.

Est-ce un problème réel dans la pratique? Quel est le meilleur moyen de choisir des nombres aléatoires dans [0, n) dérivés uniformément de la sortie de rand() , de préférence sans arithmétique en virgule flottante?

Vous avez raison, rand() % N n’est pas précisément dissortingbué de manière uniforme. Cela dépend précisément de la gamme de nombres que vous voulez et du degré d’aléatoire que vous voulez, mais si vous voulez assez d’aléatoire pour que vous en teniez compte, vous ne voulez de toute façon pas utiliser rand() . Obtenez un véritable générateur de nombres aléatoires.

Cela dit, pour obtenir une dissortingbution aléatoire réelle, modifiez la puissance suivante de 2 et échantillonnez-la jusqu’à obtenir la plage souhaitée (par exemple, pour 0-9, utilisez while(n = rand()%0x10 > 10); ) .

Cela dépend de:

  • La valeur de RAND_MAX
  • Votre valeur de N

Supposons que votre RAND_MAX est 2 ^ 32. Si N est plutôt petit (disons 2), alors le biais est 1/2 ^ 31 – ou trop petit pour être remarqué.

Mais si N est un peu plus grand, disons 2 ^ 20, alors le biais est de 1/2 ^ 12, soit environ 1 sur 4096. Beaucoup plus gros, mais quand même assez petit.

Une approche que vous pouvez faire est la suivante:

Connaissant la valeur de N , vous faites R_MAX = ((RAND_MAX + 1) / N) * N; pour l’uniformité.

Donc, vous pouvez faire votre fonction personnalisée rand() :

 int custom_rand(int mod) { int x = rand(); const int R_MAX = ((RAND_MAX + 1) / mod) * mod; while (x > R_MAX) { // discard the result if it is bigger x = rand(); } return (x % mod); } 

Il existe deux problèmes d’utilisation du rest (% n’est pas un opérateur “modulo” en C) en un nombre aléatoire uniforme sur une plage réduite. Premièrement, il existe un léger biais en faveur de nombres plus petits (mentionné ci-dessus) et, deuxièmement, les PRNG typiques ont tendance à être moins aléatoires dans les bits de poids faible. Il semble que je me souvienne de Knuth (L’Art de la Programmation, Vol II, Algorithmes Séminaires) et de l’affirmation selon laquelle (après la traduction de MIX en C) rand ()% 2 est une source médiocre de bits uniques aléatoires. Il est préférable de choisir (rand ()> RAND_MAX / 2) (ou de tester un bit de poids fort, si RAND_MAX est presque une puissance de 2.)

Le rest devrait être assez bon usage occasionnel sur de petits intervalles. Évitez-le pour les simulations. En fait, évitez rand () pour les simulations de grande taille ou les calculs de “Monte Carlo”. Les mises en œuvre ont tendance à avoir une période de l’ordre de 2 ^ 32 ou moins. Il n’est pas difficile de dépasser 4 milliards d’essais sur un processeur de 2+ GHz.