Wie kann ich nach einer Normalverteilung in C oder C ++ einfach Zufallszahlen generieren?
Ich möchte Boost nicht verwenden.
Ich weiß, dass Knuth ausführlich darüber spricht, aber ich habe seine Bücher momentan nicht zur Hand.
c++
c
random
distribution
normal-distribution
Damien
quelle
quelle
Antworten:
Es gibt viele Methoden, um aus einem regulären RNG Gauß-verteilte Zahlen zu generieren .
Die Box-Muller-Transformation wird üblicherweise verwendet. Es werden korrekt Werte mit einer Normalverteilung erzeugt. Die Mathematik ist einfach. Sie generieren zwei (einheitliche) Zufallszahlen und erhalten durch Anwenden einer Formel zwei normalverteilte Zufallszahlen. Geben Sie eine zurück und speichern Sie die andere für die nächste Anforderung einer Zufallszahl.
quelle
std::normal_distribution
genau das hinzufügt , was Sie verlangen, ohne sich mit mathematischen Details zu befassen.C ++ 11
C ++ 11 bietet
std::normal_distribution
, so würde ich heute vorgehen.C oder älter C ++
Hier sind einige Lösungen in aufsteigender Reihenfolge der Komplexität:
Addiere 12 einheitliche Zufallszahlen von 0 bis 1 und subtrahiere 6. Dies entspricht dem Mittelwert und der Standardabweichung einer normalen Variablen. Ein offensichtlicher Nachteil ist, dass der Bereich - im Gegensatz zu einer echten Normalverteilung - auf ± 6 begrenzt ist.
Die Box-Muller-Transformation. Dies ist oben aufgeführt und relativ einfach zu implementieren. Wenn Sie jedoch sehr genaue Stichproben benötigen, beachten Sie, dass die Box-Muller-Transformation in Kombination mit einigen einheitlichen Generatoren unter einer Anomalie namens Neave-Effekt 1 leidet .
Für beste Präzision empfehle ich, Uniformen zu zeichnen und die inverse kumulative Normalverteilung anzuwenden, um zu normalverteilten Variablen zu gelangen. Hier ist ein sehr guter Algorithmus für inverse kumulative Normalverteilungen.
1. HR Neave, "Zur Verwendung der Box-Muller-Transformation mit multiplikativen kongruenten Pseudozufallszahlengeneratoren", Applied Statistics, 22, 92-97, 1973
quelle
Eine schnelle und einfache Methode besteht darin, eine Anzahl gleichmäßig verteilter Zufallszahlen zu summieren und ihren Durchschnitt zu ermitteln. Im zentralen Grenzwertsatz finden Sie eine vollständige Erklärung, warum dies funktioniert.
quelle
Ich habe ein C ++ - Open Source-Projekt für den Benchmark zur Generierung normalverteilter Zufallszahlen erstellt .
Es vergleicht mehrere Algorithmen, einschließlich
cpp11random
verwendet C ++ 11std::normal_distribution
mitstd::minstd_rand
(es ist eigentlich eine Box-Muller-Transformation in Clang).Die Ergebnisse der
float
Version mit einfacher Genauigkeit ( ) auf iMac [email protected], Clang 6.1, 64-Bit:Auf Richtigkeit überprüft das Programm den Mittelwert, die Standardabweichung, die Schiefe und die Kurtosis der Proben. Es wurde festgestellt, dass die CLT-Methode durch Summieren von 4, 8 oder 16 einheitlichen Zahlen keine gute Kurtosis aufweist wie die anderen Methoden.
Der Ziggurat-Algorithmus bietet eine bessere Leistung als die anderen. Es ist jedoch nicht für die SIMD-Parallelität geeignet, da es Tabellensuche und Verzweigungen benötigt. Box-Muller mit SSE2 / AVX-Befehlssatz ist viel schneller (x1.79, x2.99) als die Nicht-SIMD-Version des Zikkurat-Algorithmus.
Daher werde ich vorschlagen, Box-Muller für die Architektur mit SIMD-Befehlssätzen zu verwenden, und kann ansonsten Zikkurat sein.
PS Der Benchmark verwendet ein einfachstes LCG-PRNG zur Erzeugung gleichmäßig verteilter Zufallszahlen. Daher ist es für einige Anwendungen möglicherweise nicht ausreichend. Der Leistungsvergleich sollte jedoch fair sein, da alle Implementierungen dasselbe PRNG verwenden, sodass der Benchmark hauptsächlich die Leistung der Transformation testet.
quelle
Hier ist ein C ++ - Beispiel, das auf einigen Referenzen basiert. Dies ist schnell und schmutzig. Sie sollten die Boost-Bibliothek nicht neu erfinden und verwenden.
Sie können ein QQ-Diagramm verwenden, um die Ergebnisse zu untersuchen und festzustellen, wie gut es einer realen Normalverteilung entspricht (ordnen Sie Ihre Stichproben 1..x, wandeln Sie die Ränge in Proportionen der Gesamtzahl von x um, dh wie viele Stichproben, erhalten Sie die z-Werte und zeichnen Sie sie auf. Eine gerade Linie nach oben ist das gewünschte Ergebnis.
quelle
Verwenden
std::tr1::normal_distribution
.Der Namespace std :: tr1 ist kein Teil von boost. Es ist der Namespace, der die Bibliothekszusätze aus dem C ++ Technical Report 1 enthält und unabhängig von Boost in aktuellen Microsoft-Compilern und gcc verfügbar ist.
quelle
So generieren Sie die Beispiele auf einem modernen C ++ - Compiler.
quelle
generator
sollte wirklich ausgesät werden.Sie können die GSL verwenden . Einige vollständige Beispiele veranschaulichen die Verwendung.
quelle
Schauen Sie sich Folgendes an: http://www.cplusplus.com/reference/random/normal_distribution/ . Dies ist der einfachste Weg, um Normalverteilungen zu erstellen.
quelle
Wenn Sie C ++ 11 verwenden, können Sie Folgendes verwenden
std::normal_distribution
:Es gibt viele andere Verteilungen, mit denen Sie die Ausgabe der Zufallszahlen-Engine transformieren können.
quelle
Ich habe die Definition des PDF unter http://www.mathworks.com/help/stats/normal-distribution.html befolgt und mir Folgendes ausgedacht :
Es ist vielleicht nicht der beste Ansatz, aber es ist ganz einfach.
quelle
rand()
vonRANDU
eine Null zurückgibt, da Ln (0) undefiniert ist.cos(2*pi*rand/RAND_MAX)
, während Sie sich mit multiplizieren(rand()%2 ? -1.0 : 1.0)
.Die FAQ-Liste von comp.lang.c bietet drei verschiedene Möglichkeiten, um auf einfache Weise Zufallszahlen mit einer Gaußschen Verteilung zu generieren.
Sie können einen Blick darauf werfen: http://c-faq.com/lib/gaussian.html
quelle
Box-Muller-Implementierung:
quelle
Es gibt verschiedene Algorithmen für die inverse kumulative Normalverteilung. Die beliebtesten in der quantitativen Finanzierung werden auf http://chasethedevil.github.io/post/monte-carlo--inverse-cumulative-normal-distribution/ getestet.
Meiner Meinung nach gibt es keinen großen Anreiz, etwas anderes als den Algorithmus AS241 von Wichura zu verwenden : Er ist maschinenpräzise, zuverlässig und schnell. Engpässe treten bei der Gaußschen Zufallszahlengenerierung selten auf.
Darüber hinaus zeigt es den Nachteil von Ziggurat-ähnlichen Ansätzen.
Die Top-Antwort hier befürwortet Box-Müller, Sie sollten sich bewusst sein, dass es bekannte Mängel gibt. Ich zitiere https://www.sciencedirect.com/science/article/pii/S0895717710005935 :
quelle
1) Die grafisch intuitive Möglichkeit, Gaußsche Zufallszahlen zu generieren, besteht in der Verwendung der Monte-Carlo-Methode. Sie würden mit Ihrem Pseudozufallszahlengenerator in C einen zufälligen Punkt in einem Feld um die Gaußsche Kurve erzeugen. Mit der Verteilungsgleichung können Sie berechnen, ob dieser Punkt innerhalb oder unterhalb der Gaußschen Verteilung liegt. Wenn dieser Punkt innerhalb der Gaußschen Verteilung liegt, haben Sie Ihre Gaußsche Zufallszahl als x-Wert des Punktes.
Diese Methode ist nicht perfekt, da die Gaußsche Kurve technisch gegen unendlich geht und Sie keine Box erstellen können, die sich in der x-Dimension der Unendlichkeit nähert. Aber die Guass'sche Kurve nähert sich in der y-Dimension ziemlich schnell 0, also würde ich mir darüber keine Sorgen machen. Die Einschränkung der Größe Ihrer Variablen in C kann Ihre Genauigkeit eher einschränken.
2) Eine andere Möglichkeit wäre die Verwendung des zentralen Grenzwertsatzes, der besagt, dass unabhängige Zufallsvariablen beim Hinzufügen eine Normalverteilung bilden. Unter Berücksichtigung dieses Theorems können Sie eine Gaußsche Zufallszahl approximieren, indem Sie eine große Anzahl unabhängiger Zufallsvariablen hinzufügen.
Diese Methoden sind nicht die praktischsten, aber das ist zu erwarten, wenn Sie keine bereits vorhandene Bibliothek verwenden möchten. Denken Sie daran, dass diese Antwort von jemandem stammt, der wenig oder keine Erfahrung mit Kalkül oder Statistik hat.
quelle
Monte-Carlo-Methode Der intuitivste Weg, dies zu tun, wäre die Verwendung einer Monte-Carlo- Methode. Nehmen Sie einen geeigneten Bereich -X, + X. Größere Werte von X führen zu einer genaueren Normalverteilung, die Konvergenz dauert jedoch länger. ein. Wählen Sie eine Zufallszahl z zwischen -X bis X. b. Halten Sie mit einer Wahrscheinlichkeit fest,
N(z, mean, variance)
wo N die Gaußsche Verteilung ist. Andernfalls fallen lassen und zu Schritt (a) zurückkehren.quelle
Schau dir an, was ich gefunden habe.
Diese Bibliothek verwendet den Ziggurat-Algorithmus.
quelle
Computer ist ein deterministisches Gerät. Es gibt keine Zufälligkeit bei der Berechnung. Darüber hinaus kann das arithmetische Gerät in der CPU die Summierung über einen endlichen Satz von Ganzzahlen (Durchführen einer Auswertung im endlichen Feld) und einen endlichen Satz von reellen rationalen Zahlen auswerten. Und auch bitweise Operationen durchgeführt. Mathe macht einen Deal mit großartigeren Mengen wie [0.0, 1.0] mit unendlich vielen Punkten.
Sie können mit einem Controller einen Draht im Computer hören, aber würde er gleichmäßige Verteilungen haben? Ich weiß es nicht. Wenn jedoch angenommen wird, dass das Signal das Ergebnis einer großen Menge unabhängiger Zufallsvariablen ist, erhalten Sie eine ungefähr normalverteilte Zufallsvariable (dies wurde in der Wahrscheinlichkeitstheorie bewiesen).
Es gibt Algorithmen, die als Pseudozufallsgenerator bezeichnet werden. Wie ich dachte, besteht der Zweck des Pseudozufallsgenerators darin, die Zufälligkeit zu emulieren. Und die Kriterien für Goodnes sind: - Die empirische Verteilung wird (in gewissem Sinne - punktuell, einheitlich, L2) zu theoretischen Werten konvergiert. - Werte, die Sie vom Zufallsgenerator erhalten, scheinen ideenabhängig zu sein. Natürlich ist es aus "realer Sicht" nicht wahr, aber wir gehen davon aus, dass es wahr ist.
Eine der beliebtesten Methoden - Sie können 12 irv mit gleichmäßigen Verteilungen summieren ... Aber um ehrlich zu sein, während der Ableitung des zentralen Grenzwertsatzes mit Hilfe der Fourier-Transformation, Taylor-Reihe, müssen einige Male n -> + inf-Annahmen getroffen werden. Zum Beispiel theoretisch - Ich persönlich verstehe nicht, wie Leute eine Summierung von 12 irv mit gleichmäßiger Verteilung durchführen.
Ich hatte Wahrscheinlichkeitstheorie in der Universität. Und besonders für mich ist es nur eine mathematische Frage. In der Universität habe ich folgendes Modell gesehen:
So wie es zu tun war, war es nur ein Beispiel. Ich denke, es gibt andere Möglichkeiten, es zu implementieren.
Der Beweis, dass es richtig ist, findet sich in diesem Buch "Moskau, BMSTU, 2004: XVI Wahrscheinlichkeitstheorie, Beispiel 6.12, S.246-247" von Krishchenko Alexander Petrovich ISBN 5-7038-2485-0
Leider weiß ich nicht, ob es eine Übersetzung dieses Buches ins Englische gibt.
quelle