nombres aléatoires distribués de façon uniforme relativement à 2 premiers

Question

Un exemple spécifique

Je dois générer un nombre aléatoire entre 0 et 2 inclus. (Ou choisir au hasard entre -1, 0 et 1).

L'approche naïve serait de faire quelque chose comme où rand() mod 3 retourne un entier rand(). Cette approche ne sera pas générer des nombres aléatoires statistiquement à moins que la limite supérieure de n'est pas <=> relativement premier (et la limite est 0 inférieure).

Par exemple, en supposant que rand () retourné 2 bits (de 0 à 3 inclus), le module serait la carte:

0 -> 0
1 -> 1
2 -> 2
3 -> 0

Cette inclinaison vers 0 serait évidemment beaucoup moins si plus de bits seraient renvoyés, mais quel que soit le biais demeureraient.

La question générique

Y at-il un moyen de génération d'un nombre aléatoire uniformément distribué entre 0 et n-1, y compris, où n est premier avec 2?

Answer 1

Une approche commune est de jeter des valeurs aléatoires au-dessus du dernier cycle complet, et il suffit de demander un nouveau numéro aléatoire.

Answer 2

Il peut être utile de choisir votre rand () limite supérieure pour être k * n où k est un nombre entier. De cette façon, le résultat sera réparti uniformément à condition que rand () est un bon générateur aléatoire.

S'il est impossible de réduire la limite supérieure, vous pouvez choisir k de telle sorte que k * n est aussi proche de rand () la limite supérieure possible et jeter les résultats ci-dessus ce numéro d'essayer à nouveau.

Answer 3

Voir ma réponse à une question similaire.

En gros, utilisez votre RNG et jeter tout ce qui précède N et essayez à nouveau. Pour l'optimisation, vous pouvez utiliser mod, et jeter tout ce qui précède étage n * (MAX / n)

Answer 4

Réponse générique: Vous devez utiliser plus que 2 bits du nombre.

Ma règle d'or est de générer des valeurs à virgule flottante, x , 0,0 <= x <1,0, multiplier par 3 et tronquer. Cela devrait vous obtenir des valeurs dans la plage 0, 1 et 2 qui dépendent d'un plus grand nombre de bits.