Pseudo-random number generation

La bibliothèque de nombres aléatoires fournit des classes qui génèrent des nombres aléatoires et pseudo-aléatoires. Ces classes incluent :

• Générateurs de bits aléatoires uniformes (URBG), qui incluent à la fois les moteurs de nombres aléatoires, qui sont des générateurs de nombres pseudo-aléatoires produisant des séquences d'entiers avec une distribution uniforme, et les générateurs de nombres véritablement aléatoires (si disponibles).
• Distributions de nombres aléatoires (par ex. uniform , normal , ou poisson distributions ) qui convertissent la sortie des URBG en diverses distributions statistiques.

Les générateurs de nombres aléatoires (URBG) et les distributions sont conçus pour être utilisés ensemble afin de produire des valeurs aléatoires. Tous les moteurs de génération de nombres aléatoires peuvent être spécifiquement initialisés, sérialisés et désérialisés pour une utilisation avec des simulateurs reproductibles.

Générateurs de bits aléatoires uniformes

Un générateur de bits aléatoire uniforme est un objet fonction retournant des valeurs entières non signées telles que chaque valeur dans la plage des résultats possibles a (idéalement) une probabilité égale d'être retournée.

Tous les générateurs de bits aléatoires uniformes satisfont aux UniformRandomBitGenerator exigences. C++20 définit également un uniform_random_bit_generator concept.

Moteurs de génération de nombres aléatoires

Un moteur de génération de nombres aléatoires (communément appelé moteur ) est un générateur uniforme de bits aléatoires qui produit des nombres pseudo-aléatoires en utilisant des données d'amorçage comme source d'entropie.

À tout moment, un moteur e de type E possède un état e i pour un entier non négatif i . Lors de sa construction, e a un état initial e 0 , qui est déterminé par les paramètres du moteur et une graine initiale (ou séquence de graines).

Les propriétés suivantes sont toujours définies pour tout type de moteur E :

• La taille de l'état de E en multiples de la taille de E::result_type (c'est-à-dire ( sizeof e i ) / sizeof ( E :: result_type ) ).
• L' algorithme de transition TA par lequel l'état e e i est avancé vers son état successeur e i+1 (c'est-à-dire TA ( e i ) == e i+1 ).
• L' algorithme de génération GA par lequel l'état de e est mappé à une valeur de type E::result_type , le résultat est un nombre pseudo-aléatoire.

Une séquence de nombres pseudo-aléatoires peut être générée en appelant alternativement TA et GA .

La bibliothèque standard fournit les implémentations de trois classes différentes d'algorithmes de génération de nombres pseudo-aléatoires sous forme de modèles de classe, permettant ainsi la personnalisation des algorithmes. Le choix du moteur à utiliser implique plusieurs compromis :

• Le générateur congruentiel linéaire est modérément rapide et nécessite un très faible stockage pour l'état.
• Le générateur de Mersenne Twister est plus lent et nécessite un stockage d'état plus important, mais avec les bons paramètres, il possède la séquence non répétitive la plus longue avec les caractéristiques spectrales les plus souhaitables (pour une définition donnée de souhaitable).
• Le générateur à soustraction avec retenue est très rapide même sur les processeurs sans jeux d'instructions arithmétiques avancés, au détriment d'un stockage d'état plus important et parfois de caractéristiques spectrales moins souhaitables.

Aucun de ces générateurs de nombres aléatoires n'est cryptographiquement sécurisé . Comme pour toute opération sécurisée, une bibliothèque cryptographique doit être utilisée à cet effet (par exemple OpenSSL RAND_bytes ).

Tous les types instanciés à partir de ces modèles satisfont aux RandomNumberEngine exigences.

Adaptateurs de moteurs de génération de nombres aléatoires

Les adaptateurs de moteur de nombres aléatoires génèrent des nombres pseudo-aléatoires en utilisant un autre moteur de nombres aléatoires comme source d'entropie. Ils sont généralement utilisés pour modifier les caractéristiques spectrales du moteur sous-jacent.

Générateurs de nombres aléatoires prédéfinis

Plusieurs algorithmes populaires spécifiques sont prédéfinis.

Nombres aléatoires non déterministes

std::random_device est un générateur de bits aléatoires uniforme non déterministe, bien que les implémentations soient autorisées à implémenter std::random_device en utilisant un moteur de nombres pseudo-aléatoires s'il n'y a pas de support pour la génération de nombres aléatoires non déterministes.

Distributions de nombres aléatoires

Une distribution de nombres aléatoires post-traite la sortie d'un URBG de telle manière que la sortie résultante soit distribuée selon une fonction de densité de probabilité statistique définie.

Les distributions de nombres aléatoires satisfont RandomNumberDistribution .

Utilitaires

Algorithmes de génération de nombres aléatoires

Bibliothèque d'aléatoire C

En plus des moteurs et distributions décrits ci-dessus, les fonctions et constantes de la bibliothèque aléatoire C sont également disponibles bien que non recommandées :

Exemple

#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <string>
int main()
{
    // Initialiser avec une valeur aléatoire réelle, si disponible
    std::random_device r;
    // Choisir une moyenne aléatoire entre 1 et 6
    std::default_random_engine e1(r());
    std::uniform_int_distribution<int> uniform_dist(1, 6);
    int mean = uniform_dist(e1);
    std::cout << "Moyenne choisie aléatoirement : " << mean << '\n';
    // Générer une distribution normale autour de cette moyenne
    std::seed_seq seed2{r(), r(), r(), r(), r(), r(), r(), r()};
    std::mt19937 e2(seed2);
    std::normal_distribution<> normal_dist(mean, 2);
    std::map<int, int> hist;
    for (int n = 0; n != 10000; ++n)
        ++hist[std::round(normal_dist(e2))];
    std::cout << "Distribution normale autour de " << mean << ":\n"
              << std::fixed << std::setprecision(1);
    for (auto [x, y] : hist)
        std::cout << std::setw(2) << x << ' ' << std::string(y / 200, '*') << '\n';
}

Moyenne choisie aléatoirement : 4
Distribution normale autour de 4 :
-4
-3
-2
-1
 0 *
 1 ***
 2 ******
 3 ********
 4 *********
 5 ********
 6 ******
 7 ***
 8 *
 9
10
11
12

Voir aussi