Ce qui suit survole les principaux mécanismes permettant de générer des nombres pseudoaélatoires avec C++ depuis C++ 11, avec un bref retour sur les mécanismes (très désuets) du langage C, qui prévalaient même (tristement) avec C++ 03.
Comment fonctionne la génération de nombres pseudoaléatoires en C++ contemporain (depuis C++ 11, donc) et en quoi est-ce une amélioration sur les pratiques du passé? C'est ce que ce petit texte vise à illustrer.
Pour illustrer notre propos, prenons un exemple simple, soit celui d'un dé à six faces qui se voudrait équitable, donc avec la même probabilité d'obtenir chacune des six valeurs possibles. Un programme simple serait :
#include <random>
#include <iostream>
#include <string>
#include <numeric>
#include <algorithm>
#include <iomanip>
#include <locale>
using namespace std;
string make_line(double proportion) {
enum { LG_LIGNE = 50 };
return string( static_cast<string::size_type>(LG_LIGNE * proportion), '*' );
}
int main() {
random_device rd;
mt19937 prng{ rd() };
enum : short { NFACES = 6 };
uniform_int_distribution<short> d6{ 1, NFACES };
enum { N = 10'000 };
short nlancers[NFACES * 2] { }; // 2..12, rien à l'entrée 0
for (short i = 0; i < N; ++i)
nlancers[d6(prng) + d6(prng) - 1]++;
// on ne tient pas compte de nlancers[0]
const auto maxval = accumulate(next(begin(nlancers)), end(nlancers), short{}, [](short x, short y) {
return max(x, y);
});
cout << "Distribution, " << N << " lancers de deux des a " << NFACES << " faces\n\n";
cout.imbue(locale{ "" });
// on ne tient pas compte de nlancers[0]
for (short i = 1; i < NFACES * 2; ++i) {
const auto nb_lancers = static_cast<double>(nlancers[i]);
const auto proportion_ligne = nb_lancers / maxval;
const auto proportion_total = nb_lancers / N * 100.0;
cout << setw(2) << i + 1 << " : " << make_line(proportion_ligne)
<< " (" << proportion_total << "%)" << endl;
}
}Quelques explications s'imposent, évidemment :
Une exécution possible de ce programme serait la suivante.
Distribution, 10000 lancers de deux des a 6 faces
2 : ******** (2,79%)
3 : **************** (5,56%)
4 : ************************ (8,22%)
5 : ******************************** (10,93%)
6 : ***************************************** (14,1%)
7 : ************************************************** (17,01%)
8 : *************************************** (13,56%)
9 : ******************************* (10,87%)
10 : ************************* (8,79%)
11 : **************** (5,66%)
12 : ******* (2,51%)Visiblement, avec une distribution uniforme et un grand nombre de paires de lancers de dés, nous obtenons essentiellement une courbe normale. C'est une bonne nouvelle!
Ce qui suit n'est pas une explication formelle de la théorie de la génération de nombres pseudoaléatoires; ce n'est qu'un survol de quelques grands principes, dans une optique d'offrir une compréhension opératoire des mécanismes concrets offerts par le langage. Pour en savoir plus, voir ../../Liens/Suggestions-lecture.html#art_computer_programming par Donald Knuth, volume 2, un livre massif qui porte exclusivement sur ce sujet. Sans blagues.
Il est impossible de générer de vrais nombres aléatoires à partir d'un algorithme au sens classique du terme, puisque ce dernier est déterministe a priori. On tire habituellement de l'entropie à travers une collecte d'information sur le monde physique (vibrations d'un disque rigide, variations de température, fréquence de pressions de touches sur le clavier, etc.) mais cette collecte d'entropie doit être réalisée par le système d'exploitation, et est donc coûteuse à obtenir pour un programme.
Pour cette raison, la génération de nombres pseudoaléatoire comprend typiquement les éléments suivants.
Un semis ou germe (en anglais : Seed) est requis pour initier le processus de génération. Ce semis vient habituellement d'une « source d'entropie » ou du moins d'une source changeante. Le nombre de secondes depuis un moment choisi dans le passé, par exemple, a beaucoup servi en ce sens (fonction std::time() du langage C), et fait un travail raisonnable si on l'appelle moins d'une fois par seconde. Aujourd'hui, piger dans l'entropie accumulée par le système d'exploitation est la norme.
Le semis est utilisé une seule fois, au démarrage du processus de génération de nombres pseudoaléatoires. Utiliser plusieurs semis n'entraîne pas une meilleure génération de nombres pseudoaléatoires (en fait, c'est plutôt le contraire qui se produit).
Notez qu'en période de tests, pour que les résultats semblent aléatoires mais demeurent prévisibles, il arrive fréquemment que l'on ait recours à un semis fixe (la valeur zéro, par exemple). En procédant ainsi, nous obtiendrons toujours les mêmes valeurs « pseudoaléatoires », dans le même ordre.
Avec C, la fonction std::srand() permet d'initialiser le semis de l'algorithme de génération qu'est std::rand(). Une implémentation possible est :
long etat_interne = {};
void srand(unsigned int seed) {
etat_interne = static_cast<long>(seed);
}Un algorithme est ensuite requis pour (a) générer un nombre pseudoaléatoire et (b) faire évoluer un état tenu à jour (et initialisé à partir du semis). L'algorithme étant déterministe, il aura une période, suite à laquelle la séquence générée se répétera.
Avec C, la fonction std::rand() sert d'algorithme de génération de nombres pseudoaléatoires. Une implémentation possible (suivant cette de std::srand() ci-dessus) est :
int rand() {
return (
(etat_interne = etat_interne * 214013L + 2531011L) >> 16
) & 0x7fff;
}Remarquez que chaque appel à std::rand() modifie l'état interne initialisé à l'origine par le semis. Du point de vue du code client, il est difficile de prédire la prochaine valeur retournée étant donné la plus récente valeur obtenue; par contre, si l'état interne était connu, on constaterait que l'algorithme est pleinement déterministe.
Le problème de fond de cette approche, telle qu'implémentée en langage C du moins, est que l'état interne est un état global susceptible d'être accédé concurremment en écriture par plusieurs threads. Elle n'est donc pas utilisable en pratique dans un système multiprogrammé.
Avec C, de plus, la période de l'algorithme est RAND_MAX, typiquement 32768, ce qui est un peu court pour des applications sérieuses.
Enfin, prendre des nombres pseudoaléatoires et les répartir selon une distribution est une tâche plus subtile qu'il n'y paraît. Par exemple, avec std::rand(), qui retourne des nombres entre 0 et RAND_MAX, une approche naïve pour tirer un nombre entre deux bornes serait :
// précondition: minval <= maxval
int lancer_de(int minval, int maxval) {
return rand() % (maxval-minval+1) + minval;
}...mais cette approche entraîne un biais, du fait qu'en général la plage de taille (maxval-minval+1) ne divisera pas exactement RAND_MAX, donc certaines valeurs apparaîtront plus souvent que d'autres en pratique. Ceci est une conséquence inacceptable pour bien des systèmes, particulièrement ceux ayant trait à la sécurité informatique. Cela explique que nos pratiques contemporaines diffèrent de celles du passé.
La mécanique de génération de nombres pseudoaléatoires avec C++ combine trois grands éléments :
L'exemple du dé à six faces, plus haut, montre une combinaison possible d'une source d'entropie (un random_device), d'un moteur (le mt19937) et d'une distribution (un uniform_int_distribution<int>). La source d'entropie est un foncteur utilisé pour générer le semis du moteur, et le moteur est utilisé par la distribution pour générer des valeurs qui seront réparties dans le respect des règles qu'elle représente. |
|
Ce qui suit est un survol de ce qu'on trouve dans <random>; pour plus de détails, voir http://en.cppreference.com/w/cpp/numeric/random
La source d'entropie standard est un random_device. Elle correspond typiquement à une source d'entropie véritable, mais peut être générée de manière pseudoaléatoire si la plateforme sous-jacente ne permet pas de faire mieux.
Sans qu'il ne s'agisse d'une source d'entropie à proprement dit, le standard offre seed_seq qui génère des entiers non-signés répartis sur un vaste intervalle en se basant sur une séquence de valeurs. Ceci peut aider à alimenter certaines sources d'entropie, mais en pratique, on l'utilise rarement de manière directe dans un programme.
Si vous souhaitez un générateur qui soit rapide, quitte à avoir une variété un peu moindre, préférez linear_congruent_engine
Les principaux moteurs de génération de nombres pseudoaléatoires sont linear_congruential_engine, mersenne_twister_engine et subtract_with_carry_engine. Certains moteurs sont des adaptateurs, et tirent leurs valeurs d'un autre moteur, par exemple ne prenant que certaines des valeurs générées par ce dernier. Il s'agit du discard_block_engine, du independent_bits_engine et du shuffle_order_engine. Il existe enfin un default_random_engine, qui varie selon les implémentations.
Il est rare qu'on les utilise directement car ces moteurs génériques doivent être paramétrés avec soin pour donner de bons résultats; on utilisera donc typiquement une version convenablement paramétrée comme celles-ci :
| Moteur générique | Moteur paramétré |
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Notez que certaines des distributions peuvent être Stateful, donc maintenir des états à l'interne. Pour cette raison, si vous passez une distribution en paramètre à une fonction, faites-le pas référence non-const
Les distributions offertes par le standard sont nombreuses.
Les distributions uniformes incluent uniform_int_distribution pour les entiers, uniform_real_distribution pour les nombres à virgule flottante et generate_canonical pour obtenir des valeurs dans .
Les distributions de Bernouilli incluent bernoulli_distribution pour des booléens. Dans le cas des entiers, on trouve binomial_distribution, negative_binomial_distribution et geometric_distribution dont les noms sont explicites.
Les distributions de Poisson incluent poisson_distribution pour des entiers. Pour les nombres à virgule flottante, on trouve exponential_distribution, gamma_distribution, weibull_distribution et extreme_value_distribution dont les noms sont explicites.
Les distributions normales offertes incluent normal_distribution, lognormal_distribution, chi_squared_distribution, cauchy_distribution, fisher_f_distribution et student_t_distribution dont les noms sont clairs et qui s'appliquent toutes à des nombres à virgule flottante.
Enfin, quelques distributions d'échantillonnage sont aussi offertes, dont discrete_distribution pour des entiers, de même que piecewise_constant_distribution et piecewise_linear_distribution qui s'appliquent à des nombres à virgule flottante et opèrent sur des intervalles.
Quelques liens pour enrichir votre compréhension du propos.
