La génération aléatoire d'entiers à partir d'une gamme

Question

J'ai besoin d'une fonction qui permettrait de générer un entier aléatoire dans la plage donnée (y compris les valeurs limites). Je n'ai pas déraisonnable qualité/aléatoire exigences, j'ai quatre exigences:

• J'ai besoin d'elle pour être rapide. Mon projet doit générer des millions (ou parfois même des dizaines de millions) de nombres aléatoires et mon générateur de courant fonction s'est avérée être un goulot d'étranglement.
• J'ai besoin d'être raisonnablement uniforme (utilisation de rand() est parfaitement bien).
• le min-max va peut être quelque chose de <0, 1> à <-32727, 32727>.
• il doit être seedable.

J'ai actuellement de code C++ suivant:

output = min + (rand() * (int)(max - min) / RAND_MAX)

Le problème, c'est qu'elle n'est pas vraiment uniforme - max est renvoyée uniquement lorsque rand() = RAND_MAX (pour Visual C++, il est 1/32727). C'est un grand problème pour les petites plages comme <-1, 1>, où la dernière valeur n'est presque jamais retourné.

J'ai donc pris la plume et du papier et est venu avec la formule suivante (qui s'appuie sur la (int)(n + 0.5) entier arrondissement truc):

Mais ça ne fonctionne toujours pas me donner une distribution uniforme. Répété fonctionne avec 10000 échantillons de me donner ratio de 37:50:13 pour les valeurs les valeurs -1, 0. 1.

Pourriez-vous proposer la meilleure formule? (ou le même ensemble de nombres pseudo-aléatoires générateur de fonction)

Answer 1

Le plus simple (et donc meilleur) C++ (à l'aide de l'2011 standard) réponse est

#include <random>

std::random_device rd;     // only used once to initialise engine
std::mt19937 rng(rd);      // random-number engine used
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased

auto random_integer = uni(rng);

Pas besoin de re-inventer la roue. Pas besoin de s'inquiéter à propos de biais. Pas besoin de s'inquiéter à propos de l'utilisation du temps comme valeur aléatoire.

Answer 2

Avez-vous essayé:

output = min + (rand() % (int)(max - min + 1))

C'est encore légèrement biaisée vers les numéros les plus bas, mais beaucoup moins qu'à votre version d'origine. Il est également possible de l'étendre pour qu'il enlève le biais.

Answer 3

Si votre compilateur prend en charge le C++0x et de l'aide c'est une option pour vous, alors la nouvelle norme <random> - tête est susceptible de répondre à vos besoins. Il a une haute qualité uniform_int_distribution qui accepte les limites minimales et maximales (inclusif que vous avez besoin), et vous pouvez choisir parmi différents générateurs de nombres aléatoires pour la prise dans la distribution.

Voici le code qui génère un million aléatoire ints distribués uniformément dans [-57, 365]. J'ai utilisé le nouveau std <chrono> des installations pour le moment comme vous l'avez mentionné la performance est une préoccupation majeure pour vous.

#include <iostream>
#include <random>
#include <chrono>

int main()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::duration<double> sec;
    Clock::time_point t0 = Clock::now();
    const int N = 10000000;
    typedef std::minstd_rand G;
    G g;
    typedef std::uniform_int_distribution<> D;
    D d(-57, 365);
    int c = 0;
    for (int i = 0; i < N; ++i) 
        c += d(g);
    Clock::time_point t1 = Clock::now();
    std::cout << N/sec(t1-t0).count() << " random numbers per second.\n";
    return c;
}

Pour moi (2,8 GHz Intel Core i5) cette affiche:

2.10268 e+07 nombres aléatoires par seconde.

Vous pouvez graine du générateur en passant dans un int à son constructeur:

    G g(seed);

Si plus tard vous trouvez qu' int ne permet pas de couvrir la gamme dont vous avez besoin pour votre distribution, cela peut être résolu en changeant l' uniform_int_distribution comme (par exemple à l' long long):

    typedef std::uniform_int_distribution<long long> D;

Si plus tard vous trouvez que l' minstd_rand n'est pas une qualité suffisante générateur, qui peut facilement être échangé. E. g.:

    typedef std::mt19937 G;  // Now using mersenne_twister_engine

Avoir un contrôle sur le générateur de nombres aléatoires, et le hasard de la distribution peut être très libérateur.

J'ai également calculé (non représentée), le premier 4 "moments" de cette distribution (à l'aide d' minstd_rand) et les a comparés aux valeurs théoriques dans une tentative de quantifier la qualité de la distribution:

min = -57
max = 365
mean = 154.131
x_mean = 154
var = 14931.9
x_var = 14910.7
skew = -0.00197375
x_skew = 0
kurtosis = -1.20129
x_kurtosis = -1.20001

( x_ Préfixe désigne les "attendus")

Answer 4

Nous allons diviser le problème en deux parties:

• Générer un nombre aléatoire n dans la plage de 0 par (max-min).
• Ajouter min pour que le numéro de

La première partie est évidemment la plus difficile. Supposons que la valeur de retour de rand() est parfaitement uniforme. À l'aide de modulo va ajouter biais pour la première (RAND_MAX + 1) % (max-min+1) numéros. Donc si on peut changer comme par magie RAND_MAX de RAND_MAX - (RAND_MAX + 1) % (max-min+1), il n'y aurait plus aucun parti pris.

Il s'avère que nous pouvons utiliser cette intuition si nous sommes disposés à permettre pseudo-non-déterminisme dans le temps d'exécution de notre algorithme. Chaque fois que rand() renvoie un nombre qui est trop grand, nous vous demandons tout simplement pour un autre nombre aléatoire jusqu'à ce que nous obtenir un qui est assez petit.

Le temps d'exécution est maintenant géométriquement distribué, avec valeur attendue 1/p où p est la probabilité d'obtenir un assez petit nombre sur le premier essai. Depuis RAND_MAX - (RAND_MAX + 1) % (max-min+1) est toujours inférieure à (RAND_MAX + 1) / 2, nous savons qu' p > 1/2, de sorte que le nombre d'itérations sera toujours moins que deux pour toute la gamme. Il devrait être possible de générer des dizaines de millions de nombres aléatoires en moins d'une seconde sur une CPU standard avec cette technique.

EDIT:

Bien que le ci-dessus est techniquement correcte, DSimon la réponse est probablement plus utile dans la pratique. Vous ne devriez pas mettre en œuvre ce genre de choses vous-même. J'ai vu beaucoup de mises en œuvre de rejet d'échantillonnage et il est souvent très difficile de voir si c'est correct ou pas.

Answer 5

Comment sur le Mersenne Twister? Le coup de pouce de la mise en œuvre est plutôt facile à utiliser et est bien testé dans de nombreuses applications du monde réel. Je l'ai utilisé moi-même dans plusieurs projets académiques tels que l'intelligence artificielle et des algorithmes évolutionnaires.

Voici l'exemple de leur vie où ils font d'une simple fonction de rouler à six côtés de mourir:

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>

boost::mt19937 gen;

int roll_die() {
    boost::uniform_int<> dist(1, 6);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
    return die();
}

Oh, et il y a plus de proxénétisme de ce générateur, juste au cas où vous n'êtes pas convaincu, vous pouvez l'utiliser en plus de la très inférieur rand():

Le Mersenne Twister est un "hasard nombre de générateurs inventé par Makoto Matsumoto et Takuji Nishimura; leur site web comprend de nombreuses les implémentations de l'algorithme.

Essentiellement, le Mersenne Twister est un très grand décalage à rétroaction linéaire vous inscrire. L'algorithme fonctionne sur un 19,937 peu de graines, de stocker dans un 624-élément de tableau de 32 bits non signé les nombres entiers. La valeur 2^19937-1 est un Nombre de Mersenne premier; la technique pour la manipulation de la semence est basé sur un anciennes "torsion" de l'algorithme, et donc le nom de "Mersenne Twister".

Un aspect séduisant de la Mersenne Twister est son utilisation de l'option binaire opérations-par opposition à la temps de multiplication -- pour générer des nombres. L'algorithme également a une très longue période, et de la bonne granularité. Il est à la fois rapide et efficace pour les non-applications cryptographiques.