Namensräume
Varianten
Aktionen

Pseudozufallszahlengenerierung

Von cppreference.com
< cpp‎ | numeric
 
C++
 
Numerik-Bibliothek
 
Pseudozufallszahlengenerierung
 

Die Bibliothek für Zufallszahlen stellt Klassen zur Erzeugung von zufälligen und pseudo-zufälligen Zahlen bereit. Diese Klassen umfassen

  • Gleichmäßige Zufallsbitgeneratoren (URBGs), die sowohl Zufallszahlengeneratoren, die Pseudo-Zufallszahlengeneratoren sind, welche Integer-Sequenzen mit einer gleichmäßigen Verteilung erzeugen, als auch echte Zufallszahlengeneratoren (falls verfügbar) umfassen.
  • Zufallszahlengenerierungsverteilungen (z.B. gleichmäßige, Normalverteilungen oder Poisson-Verteilungen), die die Ausgabe von URBGs in verschiedene statistische Verteilungen umwandeln.

URBGs und Verteilungen sind darauf ausgelegt, gemeinsam verwendet zu werden, um zufällige Werte zu erzeugen. Alle Zufallszahlengeneratoren können spezifisch initialisiert, serialisiert und deserialisiert werden, um sie mit wiederholbaren Simulatoren zu verwenden.

Inhalt

[bearbeiten] Gleichmäßige Zufallsbitgeneratoren

Ein Gleichmäßiger Zufallsbitgenerator ist ein Funktionsobjekt, das vorzeichenlose Ganzzahlwerte zurückgibt, so dass jeder Wert im Bereich der möglichen Ergebnisse (idealerweise) gleich wahrscheinlich zurückgegeben wird.

Alle gleichmäßigen Zufallsbitgeneratoren erfüllen die UniformRandomBitGenerator-Anforderungen. C++20 definiert außerdem ein uniform_random_bit_generator-Konzept.

Definiert in Header <random>
(C++20)
 spezifiziert, dass ein Typ als gleichmäßiger Zufallsbitgenerator qualifiziert ist
(Konzept) [bearbeiten]

[bearbeiten] Zufallszahlengeneratoren

Ein Zufallszahlengenerator (oft als Generator abgekürzt) ist ein gleichmäßiger Zufallsbitgenerator, der Pseudo-Zufallszahlen unter Verwendung von Seed-Daten als Entropiequelle erzeugt.

Zu jedem Zeitpunkt hat ein Generator e vom Typ E einen Zustand ei für eine nicht-negative Ganzzahl i. Bei der Konstruktion hat e einen Anfangszustand e0, der durch Generatorparameter und einen anfänglichen Seed (oder eine Seed-Sequenz) bestimmt wird.

Die folgenden Eigenschaften sind für jeden Generatortyp E immer definiert

  • Die Größe des Zustands von E in Vielfachen der Größe von E::result_type (d.h. (sizeof ei) / sizeof(E::result_type)).
  • Der Übergangs-Algorithmus TA, durch den der Zustand ei von e zu seinem Nachfolgezustand ei+1 fortgeschaltet wird (d.h. TA(ei) == ei+1).
  • Der Generierungs-Algorithmus GA, durch den der Zustand von e auf einen Wert vom Typ E::result_type abgebildet wird; das Ergebnis ist eine Pseudo-Zufallszahl.

Eine Pseudo-Zufallszahlen-Sequenz kann durch abwechselndes Aufrufen von TA und GA erzeugt werden.

Die Standardbibliothek stellt Implementierungen von drei verschiedenen Klassen von Pseudo-Zufallszahlengenerierungsalgorithmen als Klassenschablonen bereit, sodass die Algorithmen angepasst werden können. Die Wahl des zu verwendenden Generators beinhaltet eine Reihe von Kompromissen

  • Der lineare Kongruenzgenerator ist mäßig schnell und hat einen sehr geringen Speicherbedarf für den Zustand.
  • Der Mersenne-Twister-Generator ist langsamer und hat größere Speicheranforderungen für den Zustand, hat aber mit den richtigen Parametern die längste nicht-wiederholende Sequenz mit den wünschenswertesten spektralen Eigenschaften (für eine gegebene Definition von wünschenswert).
  • Der Subtraktions-mit-Übertrag-Generator ist sehr schnell, auch auf Prozessoren ohne fortgeschrittene arithmetische Befehlssätze, auf Kosten eines größeren Speicherbedarfs und manchmal weniger wünschenswerter spektraler Eigenschaften.
  • Der Philox-Generator ist ein Zähler-basierter Zufallszahlengenerator. Er hat einen kleinen Zustand und eine lange Periode (nicht weniger als 2^130) und ist für die Verwendung in Monte-Carlo-Simulationen vorgesehen, die massiv parallele Zufallszahlengenerierung erfordern. Er ist leicht vektorisierbar und parallelisierbar und wird in GPU-optimierten Bibliotheken implementiert.
 (seit C++26)

Keiner dieser Zufallszahlengeneratoren ist kryptographisch sicher. Wie bei jeder sicheren Operation sollte eine Krypto-Bibliothek für diesen Zweck verwendet werden (z.B. OpenSSL RAND_bytes).

Alle von diesen Schablonen instanziierten Typen erfüllen die RandomNumberEngine-Anforderungen.

Definiert in Header <random>
(C++11)
 implementiert den linearen Kongruenzgenerator-Algorithmus
(Klassenschablone) [bearbeiten]
(C++11)
 implementiert den Mersenne-Twister-Algorithmus
(Klassenschablone) [bearbeiten]
(C++11)
 implementiert einen Subtraktions-mit-Übertrag- (verzögerten Fibonacci)-Algorithmus
(Klassenschablone) [bearbeiten]
(C++26)
 ein zähler-basierter, parallelisierbarer Generator
(Klassenschablone) [bearbeiten]

[bearbeiten] Zufallszahlengenerator-Adapter

Zufallszahlengenerator-Adapter erzeugen Pseudo-Zufallszahlen unter Verwendung eines anderen Zufallszahlengenerators als Entropiequelle. Sie werden im Allgemeinen verwendet, um die spektralen Eigenschaften des zugrundeliegenden Generators zu ändern.

Definiert in Header <random>
(C++11)
 verwirft einige Ausgaben eines Zufallszahlengenerators
(Klassenschablone) [bearbeiten]
(C++11)
 packt die Ausgabe eines Zufallszahlengenerators in Blöcke einer bestimmten Anzahl von Bits
(Klassenschablone) [bearbeiten]
(C++11)
 liefert die Ausgabe eines Zufallszahlengenerators in einer anderen Reihenfolge
(Klassenschablone) [bearbeiten]

[bearbeiten] Vordefinierte Zufallszahlengeneratoren

Mehrere spezifische beliebte Algorithmen sind vordefiniert.

Definiert in Header <random>
Typ Definition
minstd_rand0 (C++11) std::linear_congruential_engine<std::uint_fast32_t,
                                16807, 0, 2147483647>

Entdeckt 1969 von Lewis, Goodman und Miller, 1988 von Park und Miller als "Minimalstandard" übernommen[bearbeiten]

minstd_rand (C++11)

std::linear_congruential_engine<std::uint_fast32_t,
                                48271, 0, 2147483647>
Neuer "Mindeststandard", 1993 von Park, Miller und Stockmeyer empfohlen[bearbeiten]

mt19937 (C++11)

std::mersenne_twister_engine<std::uint_fast32_t,
                             32, 624, 397, 31,
                             0x9908b0df, 11,
                             0xffffffff, 7,
                             0x9d2c5680, 15,
                             0xefc60000, 18, 1812433253>
32-Bit-Mersenne-Twister von Matsumoto und Nishimura, 1998[bearbeiten]

mt19937_64 (C++11)

std::mersenne_twister_engine<std::uint_fast64_t,
                             64, 312, 156, 31,
                             0xb5026f5aa96619e9, 29,
                             0x5555555555555555, 17,
                             0x71d67fffeda60000, 37,
                             0xfff7eee000000000, 43,
                             6364136223846793005>
64-Bit-Mersenne-Twister von Matsumoto und Nishimura, 2000[bearbeiten]

ranlux24_base (C++11) std::subtract_with_carry_engine<std::uint_fast32_t, 24, 10, 24>[bearbeiten]
ranlux48_base (C++11) std::subtract_with_carry_engine<std::uint_fast64_t, 48, 5, 12>[bearbeiten]
ranlux24 (C++11) std::discard_block_engine<std::ranlux24_base, 223, 23>

24-Bit-RANLUX-Generator von Martin Lüscher und Fred James, 1994[bearbeiten]

ranlux48 (C++11) std::discard_block_engine<std::ranlux48_base, 389, 11>

48-Bit-RANLUX-Generator von Martin Lüscher und Fred James, 1994[bearbeiten]

knuth_b (C++11) std::shuffle_order_engine<std::minstd_rand0, 256>[bearbeiten]
philox4x32 (C++26) std::philox_engine<std::uint_fast32_t, 32, 4, 10,
                   0xCD9E8D57, 0x9E3779B9,
                   0xD2511F53, 0xBB67AE85>[bearbeiten]
philox4x64 (C++26) std::philox_engine<std::uint_fast64_t, 64, 4, 10,
                   0xCA5A826395121157, 0x9E3779B97F4A7C15,
                   0xD2E7470EE14C6C93, 0xBB67AE8584CAA73B>[bearbeiten]
default_random_engine (C++11) ein implementierungsdefinierter RandomNumberEngine-Typ

[bearbeiten] Nicht-deterministische Zufallszahlen

std::random_device ist ein nicht-deterministischer gleichmäßiger Zufallsbitgenerator, obwohl Implementierungen std::random_device mit einem Pseudo-Zufallszahlengenerator implementieren dürfen, wenn keine Unterstützung für nicht-deterministische Zufallszahlengenerierung vorhanden ist.

(C++11)
 nicht-deterministischer Zufallszahlengenerator mit Hardware-Entropiequelle
(Klasse) [bearbeiten]

[bearbeiten] Zufallszahlengenerierungsverteilungen

Eine Zufallszahlengenerierungsverteilung verarbeitet die Ausgabe eines URBG so, dass die resultierende Ausgabe gemäß einer definierten statistischen Wahrscheinlichkeitsdichtefunktion verteilt ist.

Zufallszahlengenerierungsverteilungen erfüllen RandomNumberDistribution.

Definiert in Header <random>
Gleichmäßige Verteilungen
(C++11)
 erzeugt ganzzahlige Werte, die gleichmäßig über einen Bereich verteilt sind
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte, die gleichmäßig über einen Bereich verteilt sind
(Klassenschablone) [bearbeiten]
Bernoulli-Verteilungen
(C++11)
 erzeugt bool-Werte nach einer Bernoulli-Verteilung
(Klasse) [bearbeiten]
(C++11)
 erzeugt ganzzahlige Werte nach einer Binomialverteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt ganzzahlige Werte nach einer negativen Binomialverteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt ganzzahlige Werte nach einer geometrischen Verteilung
(Klassenschablone) [bearbeiten]
Poisson-Verteilungen
(C++11)
 erzeugt ganzzahlige Werte nach einer Poisson-Verteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte nach einer exponentiellen Verteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte nach einer Gamma-Verteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte nach einer Weibull-Verteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte nach einer Extremwertverteilung
(Klassenschablone) [bearbeiten]
Normalverteilungen
(C++11)
 erzeugt reelle Werte nach einer Standardnormalverteilung (Gauß-Verteilung)
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte nach einer lognormalen Verteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte nach einer Chi-Quadrat-Verteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte nach einer Cauchy-Verteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte nach einer Fisher-F-Verteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte nach einer Student'schen t-Verteilung
(Klassenschablone) [bearbeiten]
Stichprobenverteilungen
(C++11)
 erzeugt ganzzahlige Werte nach einer diskreten Verteilung
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte, die auf konstanten Teilintervallen verteilt sind
(Klassenschablone) [bearbeiten]
(C++11)
 erzeugt reelle Werte, die auf definierten Teilintervallen verteilt sind
(Klassenschablone) [bearbeiten]

[bearbeiten] Hilfsprogramme

Definiert in Header <random>
(C++11)
 verteilt reelle Werte mit gegebener Genauigkeit gleichmäßig über [​0​, 1)
(Funktionstemplate) [edit]
(C++11)
 allzweck-bias-eliminierender gesicherter Seed-Sequenzgenerator
(Klasse) [edit]

[edit] Zufallszahl-Algorithmen

Definiert in Header <random>
(C++26)
 füllt einen Bereich mit Zufallszahlen aus einem gleichmäßigen Zufalls-Bit-Generator
(Algorithmus-Funktionsobjekt)[bearbeiten]

[edit] C-Zufallsbibliothek

Zusätzlich zu den oben beschriebenen Engines und Verteilungen sind auch die Funktionen und Konstanten der C-Zufallsbibliothek verfügbar, auch wenn diese nicht empfohlen werden.

Definiert in Header <cstdlib>
 generiert eine Pseudozufallszahl
(Funktion) [edit]
 initialisiert Pseudozufallszahlengenerator
(Funktion) [edit]
 maximal möglicher Wert, der von std::rand generiert wird
(Makrokonstante) [edit]

[edit] Beispiel

Führen Sie diesen Code aus
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <string>
 
int main()
{
    // Seed with a real random value, if available
    std::random_device r;
 
    // Choose a random mean between 1 and 6
    std::default_random_engine e1(r());
    std::uniform_int_distribution<int> uniform_dist(1, 6);
    int mean = uniform_dist(e1);
    std::cout << "Randomly-chosen mean: " << mean << '\n';
 
    // Generate a normal distribution around that mean
    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 << "Normal distribution around " << mean << ":\n"
              << std::fixed << std::setprecision(1);
    for (auto [x, y] : hist)
        std::cout << std::setw(2) << x << ' ' << std::string(y / 200, '*') << '\n';
}

Mögliche Ausgabe

Randomly-chosen mean: 4
Normal distribution around 4:
-4
-3
-2
-1
 0 *
 1 ***
 2 ******
 3 ********
 4 *********
 5 ********
 6 ******
 7 ***
 8 *
 9
10
11
12

[edit] Siehe auch

C-Dokumentation für Pseudozufallszahlengenerierung
Abgerufen von "https://cppreference.de/mwiki/index.php?title=cpp/numeric/random&oldid=180395"