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
gdzie to przestrzeń probabilistyczna, a – σ–algebra borelowska.
Dla każdego przedziału prawdopodobieństwo jest ustalone przez rozkład .
Własności oczekiwane
W tej części opisujemy podstawowe miary statystyczne zmiennej losowej, takie jak wartość oczekiwana i wariancja.
Jeśli ma gęstość , to
Prawo wielkich liczb (LLN) gwarantuje zbieżność średniej do przy , a centralne tw. graniczne (CLT) – normalne odchylenie .
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
który przy zadanym ziarnie tworzy powtarzalną sekwencję. Parametry:
- Okres – najmniejsze z .
- Wymiar równomierności – równomierne pokrycie hipersześcianu .
- Test next-bit (dla RNG kryptograficznych) – nieprzewidywalność kolejnego bitu z prawdopodobieństwem istotnie .
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 | |
Serial/correlation | niezależność kolejnych wartości | współczynnik |
K–S (Kolmogorov–Smirnov) | zgodność z dystrybuantą | statystyka sup-normy |
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) | ogólne symulacje | |
std::ranlux24_base |
Tausworthe + przekładanie | obliczeniowa fizyka jądrowa | |
std::knuth_b |
LCG + shuffling | proste gry, testy | |
std::random_device |
TRNG – entropia OS | n/d | seeding, kryptografia |
Mersenne Twister. Rekurencja:
gdzie . 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 |
std::uniform_int_distribution |
||
std::uniform_real_distribution |
||
std::normal_distribution |
||
std::bernoulli_distribution |
||
std::poisson_distribution |
Dystrybucje ciągłe implementują metodę inwersji
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:
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
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. . Oczekiwana wartość , wariancja .
Rzut monetą – dystrybucja Bernoulliego
Przykład rzutu uczciwą monetą.
std::bernoulli_distribution coin(0.5);
bool isHeads = coin(gen);
Analiza. : , Var[X]=p(1-p). Dla rzutów błąd względny częstości maleje jak .
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 . .
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 . Dla i : 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:
Błąd przeciętny z . 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 :
Wersja ciągła na przedziale :
W poniższych wzorach przedstawiono momenty i funkcję generującą momenty (MGF), które charakteryzują tę dystrybucję:
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
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.
Parametry
Podstawowe parametry wpływające na położenie i rozrzut rozkładu przedstawiono poniżej:
Suma niezależnych jest również normalna:
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 ,
- odrzucaj generator jeśli dla wybranego poziomu .
Dystrybucja Bernoulliego
Dystrybucja Bernoulliego modeluje zdarzenie dychotomiczne, zwracając 1 z prawdopodobieństwem lub 0 z prawdopodobieństwem .
Parametry
Związek z rozkladem dwumianowym. Suma prób Bernoulliego prowadzi do rozkładu dwumianowego, co ilustruje związek pomiędzy tymi rozkładami:
Implementacja
double p = 0.3;
std::bernoulli_distribution B(p);
bool success = B(gen);
Przykład: 10 losowań,
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 oraz wyznaczenie przedziału ufności 95 %:
Tabela poniżej zestawia informacje o omawianych dystrybucjach, umożliwiając szybkie porównanie:
Rozkład | Kod dystr. <random> |
Parametry | Typ danych | ||
Równomierny (dyskr.) | std::uniform_int_distribution |
całkowite | |||
Normalny | std::normal_distribution |
zmiennoprzec. | |||
Bernoulli | std::bernoulli_distribution |
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:
Spektralny test równoległości daje wynik rzędu – przy wielu zastosowaniach symulacyjnych uznaje się to za „praktycznie idealne”.
Zalety
Aspekt | Wartość dodana | Komentarz matematyczny |
Okres | eliminuje cykliczność w trwałych symulacjach | |
Równomierność | 623-wymiarowa | równy rozkład punktów w hipersześcianie |
Bogactwo dystrybucji | normalna, Poissona, gamma… | każda dystrybucja to transformacja 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:
typowe stałe (glibc, MSVC):
Okres ≤ . 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 | ≤ | |
Równomierność | 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 |