C++ stellt miteinander kombinierbare Klassen zur Erzeugung (pseudo)zufälliger Zahlen (Generatoren), Saatwerte und Verteilungen bereit, deren Möglichkeiten weit über die der C-Funktion rand() aus <cstdlib> hinausgehen.
#include <ctime> #include <functional> #include <iostream> #include <random> void zufall() { #if defined(__MINGW32__) || defined(__MINGW64__) std::mt19937 engine(std::time(nullptr)); // siehe Anmerkung unten #else std::random_device rd; std::mt19937 engine(rd()); #endif std::normal_distribution<> normal; std::function<double()> random = std::bind(normal, engine); for (int i = 0; i < 20; ++i) { std::cout << random() << ' '; } }
Anmerkung: std::random_device
ist bei älteren MinGW-Compilern unter Windows noch nicht zufällig;
der Fehler wurde in g++ 9.2 behoben.1)
Die Initialisierung mit der Systemzeit std::time(nullptr)
oder "moderner", aber barocker mit
std::chrono::system_clock::now().time_since_epoch().count()
ist ein Hack für unkritische Anwendungen.
Für kryptographisch sichere Saatwerte müsste auf Mittel des Betriebssystems zurückgegriffen werden.
Zufallsgeneratoren sind Funktionsobjekte, die beim Aufruf g()
einen Ganzzahlwert aus dem geschlossenen Intervall [g.min(), g.max()]
liefern.
Ein Funktionsobjekt g
heißt Engine,
wenn es im Konstruktor eine Saatfolge übernehmen kann,
die auch über g.seed(seq)
wiederherstellbar ist.
Mit g.discard(n)
wird eine Anzahl von Zufallswerten übersprungen.
Der Zustand einer Engine lässt sich in einen Strom schreiben bzw.
aus einem Strom wiederherstellen.
Mit Vergleichsoperatoren kann die Gleichheit der Zustände geprüft werden.
std::mt19937 engine1, engine2; std::stringstream state; state << engine1; state >> engine2; assert(engine1 == engine2);
Vorgefertigte (pseudozufällige) Generator-Engines (Tabelle) sind Spezialisierungen von Schablonen, die bekannten Algorithmen folgen:
discard_block_engine<Engine, p, r>
überspringt nach r
Werten die restlichen Werte einer von der Basis-Engine erzeugten Folge aus n
Werten.independent_bits_engine<Engine, w, Zieltyp>
kombiniert w
Bits der Basis-Engine zum Zieltyp.shuffle_order_engine<Engine, k>
liefert jeweils k
Werte der Basis-Engine in veränderter Reihenfolge.
Die Qualität eines Generators hängt stark von den gewählten Konstanten ab.
Im Namensraum std
sind folgende Generatoren (Engines) definiert:
minstd_rand0 | LCG mit $a=16807$, $c=0$, $m=2^{31}-1$ |
minstd_rand | LCG mit $a=48271$, $c=0$, $m=2^{31}-1$ |
mt19937 | Mersenne-Twister 32bit |
mt19937_64 | Mersenne-Twister 64bit |
ranlux24_base | subtraktiver Generator mit Übertrag, 24bit |
ranlux48_base | subtraktiver Generator mit Übertrag, 48bit |
ranlux24 | nimmt 23 von 223 erzeugten Werten |
ranlux48 | nimmt 11 von 389 erzeugten Werten |
knuth_b | Shuffle-Algorithmus von Donald E. Knuth |
default_random_engine | implementierungsabhängiger Generator |
Saatwert-Folgen std::seed_seq s(first,last)
initialisieren Engines,
s.generate(first,last)
befüllt den angebenen Bereich [first,last)
,
s.param(out)
schreibt s.size()
Werte in den Ausgabe-Iterator out
.
std::seed_seq seed = {std::time(nullptr)}; std::vector<unsigned int> v(10); seed.generate(begin(v), end(v)); for (auto e : v) std::cout << e << ' ';
Verteilungen D(
parameter)
erzeugen mit dem Ganzzahl-Generator g
beim Aufruf d(g)
bzw. d(g, d.param())
eine Zufallszahl nach dem zugehörigen Verteilungsgesetz im Intervall [d.min(), d.max()]
.
Die Parameter p
der Verteilung lassen sich auslesen und mit d.param(p)
setzen
sowie mit I/O-Operatoren in Ströme schreiben bzw. daraus lesen.
Nach d.reset()
hängen nachfolgende Werte nicht mehr von bisher erzeugten ab.
im Namensraum std
definierte Klassen:
Verteilung (Konstruktorparameter, Vorgabewerte) | Verteilungsfunktion / Dichtefunktion | Wertebereich |
---|---|---|
Diskrete Gleichverteilunguniform_int_distribution (a = 0, b = numeric_limits<int>::max) | $P(i|a,b) = \frac{1}{b-a+1}$ | $a \leq i \leq b$ |
Stetige Gleichverteilunguniform_real_distribution (a = 0.0, b = 1.0) | $p(x|a,b) = \frac{1}{b-a}$ | $a\leq x<b$ |
Bernoulli-Verteilungbernoulli_distribution (p = 0.5) | $P(b|p) = \left\lbrace \begin{array}{l}p \\ 1-p\end{array} \right.$ | true ,false |
Binomialverteilungbinomial_distribution (n = 1, p = 0.5) | $P(i|n,p) = {n \choose i} p^i (1-p)^{n-i}$ | $0\leq i\leq n$ |
Geometrische Verteilunggeometric_distribution (p = 0.5) | $P(i|p) = p (1-p)^i$ | $0\leq i$ |
Negative Binomialverteilungnegative_binomial_distribution (n = 1, p = 0.5) | $P(i|n,p) = {n+i+1 \choose i} p^n (1-p)^i$ | $0\leq i$ |
Poisson-Verteilungpoisson_distribution (mu = 1.0) | $P(i|\mu) = \frac{e ^ \mu \mu ^i}{i!}$ | $0\leq i$ |
Exponentialverteilungexponential_distribution (lambda = 1.0) | $p(x|\lambda) = \lambda e ^{-\lambda x}$ | $0<x$ |
Gammaverteilunggamma_distribution (alpha = 1.0, beta = 1.0) | $p(x|\alpha, \beta) = \frac{e ^ {\alpha/\beta}}{\beta ^\alpha \Gamma(\alpha)}x ^{\alpha-1}$ | $0<x$ |
Weibull-Verteilungweibull_distribution (a = 1.0, b = 1.0) | $p(x|a, b) = \frac{a}{b} \left(\frac{x}{b}\right)^{a-1} e ^{-(x/b)^a}$ | $0\leq x$ |
Gumbel-Verteilungextreme_value_distribution (a = 0.0, b = 1.0) | $p(x|a, b) = \frac{1}{b} e ^{-\gamma - e^{-\gamma}}$, $\gamma = {x-a}/b$ | $x \in \mathbb{R} $ |
Normalverteilungnormal_distribution (mu = 0.0, sigma = 1.0) | $p(x|\mu, \sigma) = \frac{1}{\sigma \sqrt{2 \pi}} e ^{-\frac{(x-\mu)^2}{2 \sigma^2}}$ | $x \in \mathbb{R} $ |
Logarithmische Normalverteilunglognormal_distribution (mu = 0.0, sigma = 1.0) | $p(x|\mu, \sigma) = \frac{1}{x \sigma \sqrt{2 \pi}} e ^{-\frac{(\ln x-\mu)^2}{2 \sigma^2}}$ | $0<x$ |
Chi-Quadrat-Verteilungchisquared_distribution (n = 1) | $p(x|n) = \frac{x^{n/2 - 1} e ^{-x/2}}{\Gamma(n/2) 2^{n/2}}$ | $0<x$ |
Cauchy-Verteilungcauchy_distribution (a = 0.0, b = 1.0) | $p(x|a, b) = \frac{1}{\pi}\frac{b}{(x-a)^2+b^2}$ | $x \in \mathbb{R}$ |
F-Verteilungfisher_f_distribution (m = 1, n = 1) | $p(x|m, n) = \frac{\Gamma({m+n}/2)}{\Gamma(m/2)\Gamma(n/2)}\left(\frac{m}{n}\right)^{m/2} x^{m/2-1}(1+\frac{mx}{n})^{-{m+n}/2}$ | $0\leq x$ |
Studentsche t-Verteilungstudent_t_distribution (n = 1) | $p(x|n) = \frac{1}{\sqrt{n \pi}} \frac{\Gamma({n-1}/2)}{\Gamma(n/2)} \left(1 +\frac{x^2}{2}\right)^{-{n+1}/2}$ | $x \in \mathbb{R}$ |
discrete_distribution (firstW, lastW) | $P(i|p_0,...,p_{n-1}) = p_i$ mit $p_i = \frac{w_i}{S}$, $S=\sum_{k=0}^{n-1}{w_i}$, $w_i > 0$ | $0\leq i<n$ |
piecewise_constant_distribution (firstb, lastb, firstW) | $p(x|p_0,...,p_{n-1},\rho_0,...,\rho_{n-1}) = \frac{\rho_i}{b_{i+1}-b_i}$ mit $\rho_i = \frac{w_i}{S}$, $S= \sum_{k=0}^{n-1}{w_k}$ | $b_i\leq x<b_{i+1}$ |
Dreiecksverteilungpiecewise_linear_distribution (firstb, lastb, firstW) | $p(x|p_0,...,p_{n-1},\rho_0,...,\rho_{n-1}) = \frac{b_{i+1}-x}{b_{i+1}-b_i}\rho_i+ \frac{x-b_i}{b_{i+1}-b_i}\rho_{i+1}$ mit $\rho_i = \frac{w_i}{S}$, $S = \frac{1}{2} \sum_{k=0}^{n-1}{(w_k+w_{k+1}) (b_{k+1}-b_k)}$ | $b_i\leq x<b_{i+1}$ |