Comment générer facilement des nombres aléatoires suivant une distribution normale en C ou C ++?

Je ne veux pas utiliser Boost.

Je sais que Knuth en parle longuement mais je n'ai pas ses livres sous la main pour le moment.

Il existe de nombreuses méthodes pour générer des nombres à distribution gaussienne à partir d'un RNG régulier .

La transformée Box-Muller est couramment utilisée. Il produit correctement des valeurs avec une distribution normale. Le calcul est simple. Vous générez deux nombres aléatoires (uniformes) et en leur appliquant une formule, vous obtenez deux nombres aléatoires normalement distribués. Renvoyez-en un et enregistrez l'autre pour la prochaine demande d'un nombre aléatoire.

C ++ 11

Offres C ++ 11 std::normal_distribution, ce que j'irais aujourd'hui.

C ou C ++ plus ancien

Voici quelques solutions par ordre de complexité croissante:

1. Ajouter 12 nombres aléatoires uniformes de 0 à 1 et soustraire 6. Cela correspondra à la moyenne et à l'écart type d'une variable normale. Un inconvénient évident est que la plage est limitée à ± 6 - contrairement à une vraie distribution normale.

2. La transformation Box-Muller. Ceci est répertorié ci-dessus et est relativement simple à mettre en œuvre. Si vous avez besoin d'échantillons très précis, sachez cependant que la transformée de Box-Muller combinée à certains générateurs uniformes souffre d'une anomalie appelée Neave Effect ¹ .

3. Pour une meilleure précision, je suggère de dessiner des uniformes et d'appliquer la distribution normale cumulative inverse pour arriver à des variables normalement distribuées. Voici un très bon algorithme pour les distributions normales cumulées inverses.

^{1. HR Neave, «Sur l'utilisation de la transformation de Box-Muller avec des générateurs de nombres pseudo-aléatoires congruents multiplicatifs», Applied Statistics, 22, 92-97, 1973}

Une méthode simple et rapide consiste simplement à additionner un certain nombre de nombres aléatoires uniformément répartis et à prendre leur moyenne. Voir le théorème central des limites pour une explication complète de la raison pour laquelle cela fonctionne.

J'ai créé un projet open source C ++ pour un benchmark de génération de nombres aléatoires normalement distribués .

Il compare plusieurs algorithmes, dont

• Méthode du théorème de limite centrale
• Transformation de Box-Muller
• Méthode polaire de Marsaglia
• Algorithme de Ziggurat
• Méthode d'échantillonnage par transformée inverse.
• cpp11randomutilise C ++ 11 std::normal_distributionavec std::minstd_rand(il s'agit en fait d'une transformation Box-Muller en clang).

Les résultats de la version simple précision ( float) sur iMac [email protected], clang 6.1, 64 bits:

Pour l'exactitude, le programme vérifie la moyenne, l'écart type, l'asymétrie et l'aplatissement des échantillons. Il a été constaté que la méthode CLT en additionnant 4, 8 ou 16 nombres uniformes n'a pas un bon kurtosis comme les autres méthodes.

L'algorithme Ziggurat a de meilleures performances que les autres. Cependant, il ne convient pas au parallélisme SIMD car il nécessite une recherche de table et des branches. Box-Muller avec jeu d'instructions SSE2 / AVX est beaucoup plus rapide (x1,79, x2,99) que la version non SIMD de l'algorithme ziggurat.

Par conséquent, je suggérerai d'utiliser Box-Muller pour l'architecture avec des jeux d'instructions SIMD, et peut être ziggurat sinon.

PS le benchmark utilise un LCG PRNG le plus simple pour générer des nombres aléatoires distribués uniformes. Cela peut donc ne pas être suffisant pour certaines applications. Mais la comparaison des performances doit être juste car toutes les implémentations utilisent le même PRNG, de sorte que le benchmark teste principalement les performances de la transformation.

Voici un exemple C ++, basé sur certaines des références. C'est rapide et sale, il vaut mieux ne pas réinventer et utiliser la bibliothèque boost.

#include "math.h" // for RAND, and rand
double sampleNormal() {
    double u = ((double) rand() / (RAND_MAX)) * 2 - 1;
    double v = ((double) rand() / (RAND_MAX)) * 2 - 1;
    double r = u * u + v * v;
    if (r == 0 || r > 1) return sampleNormal();
    double c = sqrt(-2 * log(r) / r);
    return u * c;
}

Vous pouvez utiliser un diagramme QQ pour examiner les résultats et voir dans quelle mesure il se rapproche d'une distribution normale réelle (classez vos échantillons 1..x, transformez les rangs en proportions du nombre total de x, c'est-à-dire combien d'échantillons, obtenez les valeurs z et tracez-les. Une ligne droite vers le haut est le résultat souhaité).

Utilisez std::tr1::normal_distribution.

L'espace de noms std :: tr1 ne fait pas partie de boost. C'est l'espace de noms qui contient les ajouts de bibliothèque du rapport technique C ++ 1 et est disponible dans les compilateurs Microsoft et gcc à jour, indépendamment de boost.

C'est ainsi que vous générez les exemples sur un compilateur C ++ moderne.

#include <random>
...
std::mt19937 generator;
double mean = 0.0;
double stddev  = 1.0;
std::normal_distribution<double> normal(mean, stddev);
cerr << "Normal: " << normal(generator) << endl;

Vous pouvez utiliser le GSL . Quelques exemples complets sont donnés pour montrer comment l'utiliser.

Jetez un œil sur: http://www.cplusplus.com/reference/random/normal_distribution/ . C'est le moyen le plus simple de produire des distributions normales.

Si vous utilisez C ++ 11, vous pouvez utiliser std::normal_distribution:

#include <random>

std::default_random_engine generator;
std::normal_distribution<double> distribution(/*mean=*/0.0, /*stddev=*/1.0);

double randomNumber = distribution(generator);

Il existe de nombreuses autres distributions que vous pouvez utiliser pour transformer la sortie du moteur de nombres aléatoires.

J'ai suivi la définition du PDF donnée dans http://www.mathworks.com/help/stats/normal-distribution.html et j'ai trouvé ceci:

const double DBL_EPS_COMP = 1 - DBL_EPSILON; // DBL_EPSILON is defined in <limits.h>.
inline double RandU() {
    return DBL_EPSILON + ((double) rand()/RAND_MAX);
}
inline double RandN2(double mu, double sigma) {
    return mu + (rand()%2 ? -1.0 : 1.0)*sigma*pow(-log(DBL_EPS_COMP*RandU()), 0.5);
}
inline double RandN() {
    return RandN2(0, 1.0);
}

Ce n'est peut-être pas la meilleure approche, mais c'est assez simple.

La liste de FAQ comp.lang.c partage trois manières différentes de générer facilement des nombres aléatoires avec une distribution gaussienne.

Vous pouvez y jeter un œil: http://c-faq.com/lib/gaussian.html

Implémentation Box-Muller:

#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
using namespace std;
 // return a uniformly distributed random number
double RandomGenerator()
{
  return ( (double)(rand()) + 1. )/( (double)(RAND_MAX) + 1. );
}
 // return a normally distributed random number
double normalRandom()
{
  double y1=RandomGenerator();
  double y2=RandomGenerator();
  return cos(2*3.14*y2)*sqrt(-2.*log(y1));
}

int main(){
double sigma = 82.;
double Mi = 40.;
  for(int i=0;i<100;i++){
double x = normalRandom()*sigma+Mi;
    cout << " x = " << x << endl;
  }
  return 0;
}

Il existe différents algorithmes pour la distribution normale cumulative inverse. Les plus populaires en finance quantitative sont testés sur http://chasethedevil.github.io/post/monte-carlo--inverse-cumulative-normal-distribution/

À mon avis, il n'y a pas beaucoup d'incitation à utiliser autre chose que l'algorithme AS241 de Wichura : c'est la précision de la machine, fiable et rapide. Les goulots d'étranglement sont rarement dans la génération de nombres aléatoires gaussiens.

De plus, cela montre l'inconvénient des approches de type Ziggurat.

La principale réponse ici préconise Box-Müller, vous devez être conscient qu'il a des lacunes connues. Je cite https://www.sciencedirect.com/science/article/pii/S0895717710005935 :

dans la littérature, Box – Muller est parfois considéré comme légèrement inférieur, principalement pour deux raisons. Premièrement, si l'on applique la méthode de Box – Muller aux nombres d'un mauvais générateur congruentiel linéaire, les nombres transformés fournissent une couverture extrêmement pauvre de l'espace. Des graphiques de nombres transformés avec des queues en spirale peuvent être trouvés dans de nombreux livres, notamment dans le livre classique de Ripley, qui fut probablement le premier à faire cette observation "

1) Une manière graphiquement intuitive de générer des nombres aléatoires gaussiens consiste à utiliser quelque chose de similaire à la méthode de Monte Carlo. Vous généreriez un point aléatoire dans une boîte autour de la courbe gaussienne en utilisant votre générateur de nombres pseudo-aléatoires en C. Vous pouvez calculer si ce point est à l'intérieur ou en dessous de la distribution gaussienne en utilisant l'équation de la distribution. Si ce point est à l'intérieur de la distribution gaussienne, alors vous avez votre nombre aléatoire gaussien comme valeur x du point.

Cette méthode n'est pas parfaite car techniquement la courbe gaussienne continue vers l'infini, et vous ne pouvez pas créer une boîte qui s'approche de l'infini dans la dimension x. Mais la courbe guassienne s'approche assez rapidement de 0 dans la dimension y, donc je ne m'inquiéterais pas à ce sujet. La contrainte de la taille de vos variables en C peut être davantage un facteur limitant de votre précision.

2) Une autre façon serait d'utiliser le théorème central des limites qui stipule que lorsque des variables aléatoires indépendantes sont ajoutées, elles forment une distribution normale. En gardant ce théorème à l'esprit, vous pouvez approximer un nombre aléatoire gaussien en ajoutant une grande quantité de variables aléatoires indépendantes.

Ces méthodes ne sont pas les plus pratiques, mais il faut s'y attendre lorsque vous ne souhaitez pas utiliser une bibliothèque préexistante. Gardez à l'esprit que cette réponse vient de quelqu'un avec peu ou pas d'expérience en calcul ou en statistiques.

Méthode de Monte Carlo La manière la plus intuitive de le faire serait d'utiliser une méthode de Monte Carlo . Prenez une plage appropriée -X, + X. Des valeurs plus élevées de X donneront une distribution normale plus précise, mais prend plus de temps à converger. une. Choisissez un nombre aléatoire z entre -X et X. b. Restez avec une probabilité N(z, mean, variance)où N est la distribution gaussienne. Laissez tomber autrement et revenez à l'étape (a).

Jetez un œil à ce que j'ai trouvé.

Cette bibliothèque utilise l'algorithme Ziggurat.

L'ordinateur est un appareil déterministe. Il n'y a pas d'aléatoire dans le calcul. De plus, le dispositif arithmétique de la CPU peut évaluer la somme sur un ensemble fini de nombres entiers (effectuant une évaluation dans un corps fini) et un ensemble fini de nombres rationnels réels. Et a également effectué des opérations au niveau du bit. Les mathématiques prennent un accord avec des ensembles plus grands comme [0.0, 1.0] avec un nombre infini de points.

Vous pouvez écouter du fil à l'intérieur de l'ordinateur avec un contrôleur, mais aurait-il des distributions uniformes? Je ne sais pas. Mais si l'on suppose que son signal est le résultat d'accumuler des valeurs d'énormes quantités de variables aléatoires indépendantes, vous recevrez une variable aléatoire distribuée à peu près normale (cela a été prouvé dans la théorie des probabilités)

Il existe des algorithmes appelés - générateur pseudo-aléatoire. Comme je l'ai ressenti, le but du générateur pseudo aléatoire est d'émuler le caractère aléatoire. Et le critère de goodnes est: - la distribution empirique est convergée (dans un certain sens - point par point, uniforme, L2) vers théorique - les valeurs que vous recevez du générateur aléatoire semblent être indépendantes. Bien sûr, ce n'est pas vrai du «vrai point de vue», mais nous supposons que c'est vrai.

Une des méthodes les plus populaires - vous pouvez additionner 12 irv avec des distributions uniformes .... Mais pour être honnête lors de la dérivation Théorème de la limite centrale avec l'aide de la transformée de Fourier, série Taylor, il est nécessaire d'avoir n -> + inf hypothèses quelques fois. Donc, par exemple théorique - Personnellement, je ne comprends pas comment les gens effectuent une somme de 12 irv avec une distribution uniforme.

J'avais la théorie de la probilité à l'université. Et surtout pour moi, ce n'est qu'une question mathématique. À l'université, j'ai vu le modèle suivant:

double generateUniform(double a, double b)
{
  return uniformGen.generateReal(a, b);
}

double generateRelei(double sigma)
{
  return sigma * sqrt(-2 * log(1.0 - uniformGen.generateReal(0.0, 1.0 -kEps)));
}
double generateNorm(double m, double sigma)
{
  double y2 = generateUniform(0.0, 2 * kPi);
  double y1 = generateRelei(1.0);
  double x1 = y1 * cos(y2);
  return sigma*x1 + m;
}

Une telle façon de le faire n'était qu'un exemple, je suppose qu'il existe d'autres façons de le mettre en œuvre.

La preuve de son exactitude peut être trouvée dans ce livre "Moscou, BMSTU, 2004: XVI Théorie des probabilités, Exemple 6.12, p.246-247" de Krishchenko Alexander Petrovich ISBN 5-7038-2485-0

Malheureusement, je ne connais pas l'existence de la traduction de ce livre en anglais.