Génération de nombres aléatoires en C ++ 11: comment générer, comment ça marche? [fermé]

Je suis récemment tombé sur une nouvelle façon de générer des nombres aléatoires en C ++ 11, mais je n'ai pas pu digérer les articles que j'ai lus à ce sujet (qu'est-ce que ce moteur , terme mathématique comme distribution , "où tous les nombres entiers produits sont également probables ").

Alors quelqu'un peut-il expliquer

• que sont-ils?
• que signifient-ils?
• comment générer?
• comment travaillent-ils?
• etc

Vous pouvez tout appeler dans une FAQ sur la génération de nombres aléatoires.

La question est beaucoup trop large pour une réponse complète, mais permettez-moi de choisir quelques points intéressants:

Pourquoi "tout aussi probable"

Supposons que vous ayez un générateur de nombres aléatoires simple qui génère les nombres 0, 1, ..., 10 chacun avec une probabilité égale (pensez à cela comme au classique rand()). Vous voulez maintenant un nombre aléatoire dans la plage 0, 1, 2, chacun avec une probabilité égale. Votre réaction instinctive serait à prendre rand() % 3. Mais attendez, les restes 0 et 1 se produisent plus souvent que le reste 2, donc ce n'est pas correct!

C'est pourquoi nous avons besoin de distributions appropriées , qui prennent une source d'entiers aléatoires uniformes et les transforment en notre distribution souhaitée, comme Uniform[0,2]dans l'exemple. Mieux vaut laisser cela à une bonne bibliothèque!

Moteurs

Ainsi, au cœur de tout caractère aléatoire se trouve un bon générateur de nombres pseudo-aléatoires qui génère une séquence de nombres uniformément répartis sur un certain intervalle, et qui ont idéalement une très longue période. L'implémentation standard de rand()n'est pas souvent la meilleure et il est donc bon d'avoir le choix. Linear-congruential et le twister de Mersenne sont deux bons choix (LG est également souvent utilisé par rand()); encore une fois, il est bon de laisser la bibliothèque gérer cela.

Comment ça fonctionne

Facile: commencez par installer un moteur et semez-le. La graine détermine entièrement la séquence entière de nombres "aléatoires", donc a) utilisez-en une différente (par exemple prise de /dev/urandom) à chaque fois, et b) stockez la graine si vous souhaitez recréer une séquence de choix aléatoires.

#include <random>

typedef std::mt19937 MyRNG;  // the Mersenne Twister with a popular choice of parameters
uint32_t seed_val;           // populate somehow

MyRNG rng;                   // e.g. keep one global instance (per thread)

void initialize()
{
  rng.seed(seed_val);
}

Maintenant, nous pouvons créer des distributions:

std::uniform_int_distribution<uint32_t> uint_dist;         // by default range [0, MAX]
std::uniform_int_distribution<uint32_t> uint_dist10(0,10); // range [0,10]
std::normal_distribution<double> normal_dist(mean, stddeviation);  // N(mean, stddeviation)

... Et utilisez le moteur pour créer des nombres aléatoires!

while (true)
{
  std::cout << uint_dist(rng) << " "
            << uint_dist10(rng) << " "
            << normal_dist(rng) << std::endl;

}

Concurrence

Une autre raison importante à préférer <random>au traditionnel rand()est qu'il est maintenant très clair et évident de rendre la génération de nombres aléatoires sûre pour les threads: soit fournir à chaque thread son propre moteur thread-local, amorcé sur une graine locale au thread, soit synchroniser l'accès à l'objet moteur.

Divers

• Un article intéressant sur TR1 random sur codeguru.
• Wikipedia a un bon résumé (merci, @Justin).
• En principe, chaque moteur doit typedef a result_type, qui est le type d'intégrale correct à utiliser pour la graine. Je pense que j'ai eu une implémentation buggy une fois qui m'a forcé à forcer la graine pour std::mt19937to uint32_tsur x64, finalement cela devrait être corrigé et vous pouvez dire MyRNG::result_type seed_valet ainsi rendre le moteur très facilement remplaçable.

Un générateur de nombres aléatoires est une équation qui, étant donné un nombre, vous donnera un nouveau nombre. En règle générale, vous fournissez le premier numéro ou il est tiré de quelque chose comme l'heure système.

Chaque fois que vous demandez un nouveau nombre, il utilise le numéro précédent pour exécuter l'équation.

Un générateur de nombres aléatoires n'est pas considéré comme très bon s'il a tendance à produire le même nombre plus souvent que les autres nombres. c'est-à-dire si vous vouliez un nombre aléatoire entre un et 5 et que vous aviez cette distribution de nombres:

• 1: 1%
• 2: 80%
• 3: 5%
• 4: 5%
• 5: 9%

2 est généré FAR plus souvent que tout autre nombre, il est donc plus susceptible d'être produit que d'autres nombres. Si tous les nombres étaient identiques, vous auriez 20% de chances d'obtenir chaque numéro à chaque fois. Pour le dire autrement, la distribution ci-dessus est très inégale car 2 est favorisée. Une distribution avec tous les 20% serait égale.

En règle générale, si vous voulez un vrai nombre aléatoire, vous tirerez des données de quelque chose comme la météo ou d'une autre source naturelle plutôt que d'un générateur de nombres aléatoires.