Liczby losowe i generatory liczb losowych

Last modified: May 24, 2025

This article is written in: 🇵🇱

Liczby losowe i generatory liczb losowych

W języku C++ liczby losowe generuje się za pomocą standardowej biblioteki <random>. Proces losowania zaczyna się od utworzenia generatora liczb pseudolosowych, np. std::mt19937, który bazuje na algorytmie Mersenne Twister. Aby uzyskać bardziej losowe wyniki, generator inicjalizuje się za pomocą unikalnej wartości, zwaną "ziarnem" (ang. seed), co można zrobić np. poprzez std::random_device. Następnie używa się odpowiednich dystrybucji, takich jak std::uniform_int_distribution (dla liczb całkowitych z równomiernym rozkładem) lub std::uniform_real_distribution (dla liczb zmiennoprzecinkowych), aby wygenerować liczby z określonego zakresu. Dzięki tej bibliotece losowanie w C++ jest bardziej elastyczne i daje kontrolę nad różnymi aspektami generowania liczb losowych, w tym nad zakresem i typem wartości.

┌──────────────────────────────────────────┐
│          Generator liczb losowych        │
│  (std::random_device, std::mt19937 itp.) │
└──────────────────────────────────────────┘
                │           ▲
                │ surowe    │ ziarno
                │ bity      │ (opcjonalnie)
                ▼           │
╔═════════════════════════════════════════╗
║   Sekwencja losowych bitów / liczb      ║
╚═════════════════════════════════════════╝
                │
                │ źródło entropii
                ▼
┌─────────────────────────────────────────┐
│             Dystrybucja                 │
│ (std::uniform_int_distribution,         │
│  std::normal_distribution itp.)         │
└─────────────────────────────────────────┘
                │
                │ przekształcenie na
                │ określony rozkład
                ▼
╔═══════════════════════════════════════════════╗
║   Gotowe liczby losowe w zadanym rozkładzie   ║
╚═══════════════════════════════════════════════╝

Liczby losowe

Teraz zapoznamy się z matematycznymi podstawami pojęcia liczby losowej, definiując zmienne losowe oraz ich rozkłady.

W klasycznej teorii prawdopodobieństwa liczbę losową modeluje zmienna losowa

$X : (Ω, F, P) ⟶ (R, B)$

gdzie $(Ω, F, P)$ to przestrzeń probabilistyczna, a $B$ – σ–algebra borelowska.

Dla każdego przedziału $A \subseteq R$ prawdopodobieństwo $P! (X \in A)$ jest ustalone przez rozkład $F_{X} (x) = P (X \leq x)$ .

Własności oczekiwane

W tej części opisujemy podstawowe miary statystyczne zmiennej losowej, takie jak wartość oczekiwana i wariancja.

Jeśli $X$ ma gęstość $f_{X}$ , to

$E [X] = \int_{- \infty}^{\infty} x f_{X} (x) d x$

$V a r [X] = \int_{- \infty}^{\infty} (x - E [X])^{2} f_{X} (x) d x$

Prawo wielkich liczb (LLN) gwarantuje zbieżność średniej ${\bar{X}}_{n}$ do $E [X]$ przy $n \to \infty$ , a centralne tw. graniczne (CLT) – normalne odchylenie $O (n^{- 1 / 2})$ .

Prawdziwa losowość vs. pseudolosowość

Teraz omówimy różnice pomiędzy rzeczywistymi źródłami losowości a deterministycznymi generatorami pseudolosowymi.

Źródła entropii

Prawdziwe RNG (TRNG). Oparte na zjawiskach fizycznych: szum termiczny, promieniotwórczość, odchylenia czasu taktowania CPU.
Generator pseudolosowy (PRNG). Deterministyczny algorytm

$s_{k + 1} = F (s_{k}) (\mod m), X_{k} = g (s_{k})$

który przy zadanym ziarnie $s_{0}$ tworzy powtarzalną sekwencję. Parametry:

Okres $p$ – najmniejsze $k > 0$ z $s_{n + k} = s_{n}$ .
Wymiar równomierności – równomierne pokrycie hipersześcianu $[0, 1)^{d}$ .
Test next-bit (dla RNG kryptograficznych) – nieprzewidywalność kolejnego bitu z prawdopodobieństwem istotnie $> \frac{1}{2}$ .

Statystyczne testy jakości

Poniższa tabela przedstawia główne klasy testów statystycznych używanych do oceny generatorów pseudolosowych:

Klasa testu	Weryfikowana własność	Metryka
Chi-kwadrat	jednorodność histogramu	$χ^{2} = \sum \frac{(O_{i} - E_{i})^{2}}{E_{i}}$
Serial/correlation	niezależność kolejnych wartości	współczynnik $r = \frac{C o v (X_{i}, X_{i + k})}{σ^{2}}$
K–S (Kolmogorov–Smirnov)	zgodność z dystrybuantą $F$	statystyka sup-normy $D_{n}$
DieHard / TestU01	złożone właściwości	zbiór 20–100 testów

Sekwencja testów nie dowodzi losowości, lecz obala ją, gdy statystyki wyjdą poza akceptowalny przedział ufności.

Generowanie liczb losowych

Teraz przedstawimy dostępne w C++ generatory liczb losowych oraz ich główne właściwości i zastosowania.

Przegląd generatorów

Generator	Algorytm	Okres	Zastosowania
`std::mt19937`	Mersenne Twister (19937-bit)	$2^{19937} - 1$	ogólne symulacje
`std::ranlux24_base`	Tausworthe + przekładanie	$\approx 10^{171}$	obliczeniowa fizyka jądrowa
`std::knuth_b`	LCG + shuffling	$2^{64}$	proste gry, testy
`std::random_device`	TRNG – entropia OS	n/d	seeding, kryptografia

Mersenne Twister. Rekurencja:

$x_{k + n} = x_{k + m} \oplus ((x_{k}^{upper} ‖ x_{k + 1}^{lower}) \cdot A),$

gdzie $n = 624, m = 397$ . Duży okres i 623-wymiarowa równomierność zapewniają dobry rozkład w praktyce nie-krypto.

Dystrybucje

W tej części omówione zostaną najważniejsze dystrybucje dostępne w bibliotece <random> oraz ich własności.

Dystrybucja	Parametry	Gęstość/PMF $f (x)$
`std::uniform_int_distribution`	$a, b \in Z$	$f (k) = \frac{1}{b - a + 1}$
`std::uniform_real_distribution`	$a, b \in R$	$f (x) = \frac{1}{b - a}$
`std::normal_distribution`	$μ, σ$	$f (x) = \frac{1}{\sqrt{2 π} σ} e^{- \frac{(x - μ)^{2}}{2 σ^{2}}}$
`std::bernoulli_distribution`	$p$	$f (1) = p,; f (0) = 1 - p$
`std::poisson_distribution`	$λ$	$f (k) = e^{- λ} \frac{λ^{k}}{k!}$

Dystrybucje ciągłe implementują metodę inwersji

$X = F^{- 1} (U) z U \sim U (0, 1)$

lub transformacje specjalne (np. Box-Muller).

Inicjalizacja – właściwości ziarna

Omówimy, jak dobór ziarna wpływa na powtarzalność oraz jakość generowanych sekwencji.

Jeśli dwa generatory otrzymają to samo seed, ich sekwencje będą identyczne:

$\forall n x_{n}^{(1)} = x_{n}^{(2)} .$

W symulacjach replikowalnych podajemy jawnie wartość seeda; w sytuacjach wymagających nieprzewidywalności (kryptografia) używamy std::random_device.

Przykłady użycia (C++ 17)

Poniżej znajdują się przykłady wykorzystania biblioteki <random> w praktycznych scenariuszach, ilustrujące różne zastosowania dystrybucji.

Liczba z przedziału $[a, b] \subset Z$

Wygenerujemy liczbę całkowitą z zadanego przedziału.

std::mt19937 gen(std::random_device{}());
std::uniform_int_distribution<int> dist(a,b);
int x = dist(gen);

Własności. $Pr X = k = 1 / (b - a + 1)$ . Oczekiwana wartość $E [X] = \frac{a + b}{2}$ , wariancja $σ^{2} = \frac{(b - a + 1)^{2} - 1}{12}$ .

Rzut monetą – dystrybucja Bernoulliego

Przykład rzutu uczciwą monetą.

std::bernoulli_distribution coin(0.5);
bool isHeads = coin(gen);

Analiza. $X \sim B e r n (p)$ : $E [X] = p$ , Var[X]=p(1-p). Dla $n$ rzutów błąd względny częstości maleje jak $O! (n^{- 1 / 2})$ .

Rzut sześciościenną kostką

Generowanie wyrzutu kostki o sześciu ściankach.

std::uniform_int_distribution<int> d6(1,6);
int result = d6(gen);

Rozkład dyskretny równomierny na $1, \dots, 6$ . $E [X] = 3.5,; σ^{2} = \frac{35}{12}$ .

Generator silnych haseł

Przykład tworzenia losowego hasła o zadanej długości.

std::string alphabet =
    "abcdefghijklmnopqrstuvwxyz"
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    "0123456789!@#$%^&*()-_=+";
std::uniform_int_distribution<size_t> pick(0, alphabet.size()-1);

auto password = [&] (size_t n) {
    std::string s;
    for(size_t i=0;i<n;++i) s+=alphabet[pick(gen)];
    return s;
};

Entropia hasła $H = n \log_{2} | alphabet |$ . Dla $n = 12$ i $| a l p h a b e t | = 74$ : $H \approx 71$ bitów.

Metody Monte Carlo

Demonstracja estymacji całki przy pomocy losowania.

std::uniform_real_distribution<double> U(a,b);
double sum = 0;
for(size_t k=0;k<N;++k) sum += g(U(gen));
double I = (b-a)*sum/N;

Symulacyjna estymata całki:

$I = \int_{a}^{b} g (x) d x, {\hat{I}}_{N} = (b - a) \frac{1}{N} \sum_{k = 1}^{N} g (U_{k}), U_{k} \sim U (a, b) .$

Błąd przeciętny $R M S E = σ / \sqrt{N}$ z $σ^{2} = V a r [g (U)]$ . Uwaga. Dla funkcji silnie oscylujących warto stosować ważoną próbę (importance sampling) lub stratyfikację.

RNG kryptograficzne (CSPRNG)

Wymagania formalne (Goldwasser–Micali):

Jednokierunkowość – brak efektywnego algorytmu do odtworzenia seeda.
Test next-bit –

$$ \Pr[G(x)i = 1 \mid G(x)_1, G(x)_2, \dots, G(x){i-1}] = \frac{1}{2} \pm \varepsilon(\lambda). $$

gdzie $ε$ jest zaniedbywalne względem parametru bezpieczeństwa $λ$ .

W C++20 brak oficjalnego CSPRNG, ale popularne biblioteki (libsodium, Botan) udostępniają randombytes_buf, crypto_rng. Dla systemowego źródła entropii można użyć:

#include <openssl rand.h="">
unsigned char buf[32];
RAND_bytes(buf, sizeof(buf)); // 256-bit

Zastosowanie różnych dystrybucji

Teraz omówimy zastosowania kilku dystrybucji losowych dostępnych w bibliotece <random>, prezentując ich definicje, własności, implementację w C++ oraz przykłady użycia.

Dystrybucja równomierna

Dystrybucja równomierna generuje wartości o jednakowym prawdopodobieństwie w całym zakresie, co jest przydatne, gdy potrzebujemy równomiernie rozłożyć próbki.

Dyskretna wersja na zbiorze kolejnych liczb całkowitych $a, \dots, b$ :

$P (X = k) = \frac{1}{b - a + 1}, k = a, \dots, b$

Wersja ciągła na przedziale $[a, b]$ :

$f (x) = \frac{1}{b - a} 1_{[a, b]} (x)$

$F (x) = \frac{x - a}{b - a}$

W poniższych wzorach przedstawiono momenty i funkcję generującą momenty (MGF), które charakteryzują tę dystrybucję:

$E [X] = \frac{a + b}{2}$

$V a r [X] = \frac{(b - a)^{2}}{12}$

$M_{X} (t) = \frac{e^{t b} - e^{t a}}{t (b - a)} (t \neq 0)$

Implementacja

std::mt19937 gen(std::random_device{}());
std::uniform_int_distribution<int> U(a,b);
int k = U(gen);

Rada. Generator wywołuj raz i przekazuj referencję; kosztowna inicjalizacja std::random_device{} nie powinna znajdować się w pętli.

Przykład: 10 liczb w zakresie $[1, 100]$

Poniżej przykład wylosowania dziesięciu liczb z przedziału [1,100]:

std::cout << "Uniform[1,100]: ";
for(int i=0;i<10;++i) std::cout << U(gen) << ' ';

Dystrybucja normalna (Gaussa)

Rozkład normalny, zwany też Gaussa, opisuje zmienną losową o gęstości dzwonowej i jest uzywany w statystyce ze względu na centralne twierdzenie graniczne.

$f (x) = \frac{1}{\sqrt{2 π} σ} \exp! [- \frac{(x - μ)^{2}}{2 σ^{2}}], x \in R$

Parametry

Podstawowe parametry wpływające na położenie i rozrzut rozkładu przedstawiono poniżej:

$E [X] = μ$

$V a r [X] = σ^{2}$

$M_{X} (t) = \exp! (μ t + \frac{1}{2} σ^{2} t^{2})$

Suma niezależnych $X_{i} \sim N (μ_{i}, σ_{i}^{2})$ jest również normalna:

$\sum_{i} X_{i} \sim N! (\sum μ_{i}, \sum σ_{i}^{2})$

Implementacja

std::normal_distribution<double> N(mu, sigma);
double x = N(gen);

Przykład generowania próbek z rozkładu normalnego o zadanych parametrach:

std::cout << "Normal(50,10): ";
for(int i=0;i<10;++i) std::cout << N(gen) << ' ';

Weryfikacja. Aby sprawdzić poprawność generatora, warto przeprowadzić prostą weryfikację statystyczną:

zbuduj histogram,

oblicz statystykę K–S $D_{n} = sup_{x} | F_{n} (x) - Φ_{μ, σ} (x) |$ ,

odrzucaj generator jeśli $D_{n} > D_{α, n}$ dla wybranego poziomu $α$ .

Dystrybucja Bernoulliego

Dystrybucja Bernoulliego modeluje zdarzenie dychotomiczne, zwracając 1 z prawdopodobieństwem $p$ lub 0 z prawdopodobieństwem $1 - p$ .

$P (X = 1) = p, P (X = 0) = 1 - p, 0 < p < 1.$

Parametry

$E [X] = p$

$V a r [X] = p (1 - p)$

$M_{X} (t) = 1 - p + p e^{t}$

Związek z rozkladem dwumianowym. Suma prób Bernoulliego prowadzi do rozkładu dwumianowego, co ilustruje związek pomiędzy tymi rozkładami:

$\sum_{i = 1}^{n} X_{i} \sim B i n (n, p) .$

Implementacja

double p = 0.3;
std::bernoulli_distribution B(p);
bool success = B(gen);

Przykład: 10 losowań, $p = 0, 3$

Przykład wykonania dziesięciu niezależnych prób Bernoulliego:

for(int i=0;i<10;++i) std::cout << B(gen) << ' ';

Analiza częstości. Analiza częstościowa pozwala na ocenę zbieżności częstości względnej do $p$ oraz wyznaczenie przedziału ufności 95 %:

$\hat{p} \pm 1.96 \sqrt{p (1 - p) / n}$

Tabela poniżej zestawia informacje o omawianych dystrybucjach, umożliwiając szybkie porównanie:

Rozkład	Kod dystr. `<random>`	Parametry	$E [X]$	$V a r [X]$	Typ danych
Równomierny (dyskr.)	`std::uniform_int_distribution`	$a, b$	$\frac{a + b}{2}$	$\frac{(b - a + 1)^{2} - 1}{12}$	całkowite
Normalny	`std::normal_distribution`	$μ, σ$	$μ$	$σ^{2}$	zmiennoprzec.
Bernoulli	`std::bernoulli_distribution`	$p$	$p$	$p (1 - p)$	bool/int

Zalety i wady różnych metod

Teraz porównamy najpopularniejsze metody generowania liczb losowych w C++, omawiając ich zalety oraz ograniczenia w różnych zastosowaniach.

`std::random` (C++11)

Biblioteka <random> w C++11 dostarcza elastyczny interfejs „generator + dystrybucja” bazujący domyślnie na std::mt19937. Poniżej przyjrzymy się matematycznemu modelowi Mersenne Twistera wraz z jego mocnymi i słabymi stronami.

Model matematyczny

Domyślny wybór – std::mt19937 – jest implementacją algorytmu Mersenne Twistera:

$\begin{aligned} x_{k + n} & = x_{k + m} \oplus ((x_{k}^{u} ∥ x_{k + 1}^{ℓ}) A), \\ n & = 624, m = 397, \\ okres & = 2^{19937} - 1 \approx 10^{6001}, \\ d_{max} & = 623 (wymiar równomierności). \end{aligned}$

Spektralny test równoległości daje wynik rzędu $2^{- 2018}$ – przy wielu zastosowaniach symulacyjnych uznaje się to za „praktycznie idealne”.

Zalety

Aspekt	Wartość dodana	Komentarz matematyczny
Okres	$2^{19937} - 1$	eliminuje cykliczność w trwałych symulacjach
Równomierność	623-wymiarowa	równy rozkład punktów w hipersześcianie $[0, 1)^{623}$
Bogactwo dystrybucji	normalna, Poissona, gamma…	każda dystrybucja to transformacja $X = F^{- 1} (U)$ lub specjalny algorytm
Konfigurowalne ziarno	deterministyczne lub `random_device`	replikowalność lub entropia systemowa
Przenośność	zdefiniowane przez ISO/IEC 14882	identyczna sekwencja dla tego samego seeda na wszystkich kompilatorach

Wady

Trzeba rozumieć dwustopniowy model: generator + dystrybucja.
Brak odporności kryptograficznej – Mersenne Twister jest liniowy nad $\mathbb F_2$; stan generatora (19937 bitów) można odtworzyć na podstawie 19937 kolejnych wyjść.
Koszt inicjalizacji – std::random_device może być wolny (blokuje podczas odczytu z /dev/urandom).
Rozmiar stanu – 2,5 KB dla mt19937; przy wielu wątkach oznacza to znaczną ilość pamięci.

`rand()` – klasyczny LCG

Funkcja rand() to prosty liniowy kongruentny generator (LCG) o minimalnym API, często używany dla szybkiego startu, ale z istotnymi ograniczeniami.

Model matematyczny

Większość implementacji to liniowy generator:

$x_{n + 1} = (a x_{n} + c) mod m,$

typowe stałe (glibc, MSVC):

$a = 1103515245, c = 12345, m = 2^{31} .$

Okres ≤ $m = 2^{31}; (\approx 2.1 \cdot 10^{9})$ . Najmłodszy bit ma okres 2, co czyni go bezużytecznym w symulacjach binarnych.

Zalety

Aspekt	Argument	Uwaga
Minimalne API	`int r = rand();`	brak szablonów ↔ szybki start
Dostępność	C89 / C++98	działanie na wbudowanych systemach, bibliotece `libc`
Przepustowość	jedna operacja mnożenia + dodawania	przeciętnie 2–3× szybciej od `mt19937` (zależnie od CPU)

Wady

Krótki okres generacji – przy prędkości 10⁸ liczb/s pełny cykl wyczerpuje się w ok. 21 s.
Słabe własności spektralne – pojawiają się korelacje w przestrzeni 3D w symulacjach Monte Carlo.
Niejednorodność implementacji – różne kompilatory używają odmiennych stałych.
Brak wbudowanych rozkładów – konieczne ręczne przekształcenia (np. metoda Box–Mullera).
Łamliwość kryptograficzna – na podstawie zaledwie trzech wyjść można odzyskać parametry generatora.

Zestawienie porównawcze

Poniżej tabela podsumowująca różnice między std::mt19937 a rand():

Kryterium	`std::mt19937`	`rand()` (LCG)
Okres	$2^{19937} - 1$	≤ $2^{31}$
Równomierność $d_{max}$	623	≤ 5
Koszt generacji	\~10 ns	\~5 ns
Rozmiar stanu	2,5 KB	4 B
Kryptografia	❌ (liniowość)	❌
Wbudowane dystrybucje	✔ (\~20)	❌
Standaryzacja seeda	✔ (deterministyczna)	❌
Łatwość użycia	umiarkowana	wysoka