Pseudo-random number generation

Die Zufallszahlenbibliothek bietet Klassen, die Zufalls- und Pseudozufallszahlen erzeugen. Diese Klassen umfassen:

• Uniforme Zufallsbitgeneratoren (URBGs), die sowohl Zufallszahlengeneratoren (Engines), welche pseudozufällige Zahlenfolgen mit einer Gleichverteilung erzeugen, als auch echte Zufallszahlengeneratoren (falls verfügbar) umfassen.
• Zufallszahlenverteilungen (z.B. uniform , normal , oder poisson distributions ), die die Ausgabe von URBGs in verschiedene statistische Verteilungen umwandeln.

URBGs und Verteilungen sind dafür konzipiert, gemeinsam verwendet zu werden, um Zufallswerte zu erzeugen. Alle Zufallszahlengeneratoren können gezielt gesät, serialisiert und deserialisiert werden, um mit wiederholbaren Simulatoren verwendet zu werden.

Gleichmäßige Zufallsbitgeneratoren

Ein uniform random bit generator ist ein Funktionsobjekt, das vorzeichenlose Ganzzahlwerte zurückgibt, sodass jeder Wert im Bereich der möglichen Ergebnisse (idealiter) eine gleiche Wahrscheinlichkeit hat, zurückgegeben zu werden.

Alle gleichförmigen Zufallsbitgeneratoren erfüllen die UniformRandomBitGenerator Anforderungen. C++20 definiert ebenfalls ein uniform_random_bit_generator Konzept.

Zufallszahlengeneratoren

Eine Zufallszahlen-Engine (häufig abgekürzt als Engine ) ist ein gleichmäßiger Zufallsbitgenerator, der pseudozufällige Zahlen unter Verwendung von Seed-Daten als Entropiequelle erzeugt.

Zu jedem beliebigen Zeitpunkt hat eine Engine e vom Typ E einen Zustand e i für eine nicht-negative Ganzzahl i . Bei der Konstruktion erhält e einen Anfangszustand e 0 , der durch Engine-Parameter und einen initialen Seed (oder Seed-Sequenz) bestimmt wird.

Die folgenden Eigenschaften sind für jeden Maschinentyp E stets definiert:

• Die Größe des Zustands von E in Vielfachen der Größe von E::result_type (d.h. ( sizeof e i ) / sizeof ( E :: result_type ) ).
• Der Übergangsalgorithmus TA , durch den e ’s Zustand e i zu seinem Nachfolgezustand e i+1 weiterentwickelt wird (d.h. TA ( e i ) == e i+1 ).
• Der Generierungsalgorithmus GA , durch den e ’s Zustand auf einen Wert des Typs E::result_type abgebildet wird; das Ergebnis ist eine Pseudozufallszahl.

Eine Pseudo-Zufallszahlenfolge kann durch abwechselnden Aufruf von TA und GA erzeugt werden.

Die Standardbibliothek bietet die Implementierungen von drei verschiedenen Klassen von Pseudo-Zufallszahlengenerierungsalgorithmen als Klassentemplates an, sodass die Algorithmen angepasst werden können. Die Auswahl, welche Engine verwendet werden soll, beinhaltet eine Reihe von Abwägungen:

• Die Linear Congruential Engine ist mäßig schnell und hat einen sehr geringen Speicherbedarf für den Zustand.
• Die Mersenne Twister Engine ist langsamer und hat höhere Zustandsspeicheranforderungen, bietet jedoch bei richtiger Parametereinstellung die längste nicht-wiederholende Sequenz mit den besten spektralen Eigenschaften (für eine gegebene Definition von "wünschenswert").
• Die Subtract With Carry Engine ist sehr schnell, selbst auf Prozessoren ohne erweiterte Arithmetik-Befehlssätze, auf Kosten von größerem Zustandsspeicher und manchmal weniger wünschenswerten spektralen Eigenschaften.

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

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

Zufallszahlengenerator-Adapter

Zufallszahlen-Engine-Adapter erzeugen Pseudo-Zufallszahlen unter Verwendung einer anderen Zufallszahlen-Engine als Entropiequelle. Sie werden im Allgemeinen verwendet, um die spektralen Eigenschaften der zugrundeliegenden Engine zu verändern.

Vordefinierte Zufallszahlengeneratoren

Mehrere spezifische populäre Algorithmen sind vordefiniert.

Nicht-deterministische Zufallszahlen

std::random_device ist ein nicht-deterministischer gleichförmiger Zufallsbitgenerator, obwohl Implementierungen es erlaubt ist, std::random_device unter Verwendung eines Pseudozufallszahlengenerators zu implementieren, wenn keine Unterstützung für nicht-deterministische Zufallszahlengenerierung vorhanden ist.

Zufallszahlenverteilungen

Eine Zufallszahlenverteilung verarbeitet die Ausgabe eines URBG nach, sodass die resultierende Ausgabe gemäß einer definierten statistischen Wahrscheinlichkeitsdichtefunktion verteilt ist.

Zufallszahlenverteilungen erfüllen die Anforderungen RandomNumberDistribution .

Dienstprogramme

Zufallszahlenalgorithmen

C-Zufallsbibliothek

Zusätzlich zu den oben beschriebenen Engines und Verteilungen sind auch die Funktionen und Konstanten aus der C-Random-Bibliothek verfügbar, obwohl nicht empfohlen:

Beispiel

#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <random>
#include <string>
int main()
{
    // Mit einem echten Zufallswert initialisieren, falls verfügbar
    std::random_device r;
    // Einen zufälligen Mittelwert zwischen 1 und 6 wählen
    std::default_random_engine e1(r());
    std::uniform_int_distribution<int> uniform_dist(1, 6);
    int mean = uniform_dist(e1);
    std::cout << "Zufällig gewählter Mittelwert: " << mean << '\n';
    // Eine Normalverteilung um diesen Mittelwert generieren
    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 << "Normalverteilung um " << mean << ":\n"
              << std::fixed << std::setprecision(1);
    for (auto [x, y] : hist)
        std::cout << std::setw(2) << x << ' ' << std::string(y / 200, '*') << '\n';
}

Zufällig gewählter Mittelwert: 4
Normalverteilung um 4:
-4
-3
-2
-1
 0 *
 1 ***
 2 ******
 3 ********
 4 *********
 5 ********
 6 ******
 7 ***
 8 *
 9
10
11
12

Siehe auch