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 AR prawdopodobieństwo P!(XA) jest ustalone przez rozkład FX(x)=P(Xx).

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ść fX, to

E[X]=xfX(x)dx

Var[X]=(xE[X])2fX(x)dx

Prawo wielkich liczb (LLN) gwarantuje zbieżność średniej X¯n do E[X] przy n, a centralne tw. graniczne (CLT) – normalne odchylenie O(n1/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

sk+1=F(sk)(modm),Xk=g(sk)

który przy zadanym ziarnie s0 tworzy powtarzalną sekwencję. Parametry:

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=(OiEi)2Ei
Serial/correlation niezależność kolejnych wartości współczynnik r=Cov(Xi,Xi+k)σ2
K–S (Kolmogorov–Smirnov) zgodność z dystrybuantą F statystyka sup-normy Dn
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) 2199371 ogólne symulacje
std::ranlux24_base Tausworthe + przekładanie 10171 obliczeniowa fizyka jądrowa
std::knuth_b LCG + shuffling 264 proste gry, testy
std::random_device TRNG – entropia OS n/d seeding, kryptografia

Mersenne Twister. Rekurencja:

xk+n=xk+m((xkupperxk+1lower)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,bZ f(k)=1ba+1
std::uniform_real_distribution a,bR f(x)=1ba
std::normal_distribution μ,σ f(x)=12πσe(xμ)22σ2
std::bernoulli_distribution p f(1)=p,;f(0)=1p
std::poisson_distribution λ f(k)=eλλkk!

Dystrybucje ciągłe implementują metodę inwersji

X=F1(U) z UU(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:

nxn(1)=xn(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]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. PrX=k=1/(ba+1). Oczekiwana wartość E[X]=a+b2, wariancja σ2=(ba+1)2112.

Rzut monetą – dystrybucja Bernoulliego

Przykład rzutu uczciwą monetą.

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

Analiza. XBern(p): E[X]=p, Var[X]=p(1-p). Dla n rzutów błąd względny częstości maleje jak O!(n1/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,,6. E[X]=3.5,;σ2=3512.

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=nlog2|alphabet|. Dla n=12 i |alphabet|=74: H71 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=abg(x)dx,I^N=(ba)1Nk=1Ng(Uk),UkU(a,b).

Błąd przeciętny RMSE=σ/N z σ2=Var[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):

  1. Jednokierunkowość – brak efektywnego algorytmu do odtworzenia seeda.
  2. 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,,b:

P(X=k)=1ba+1,k=a,,b

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

f(x)=1ba1[a,b](x)

F(x)=xaba

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

E[X]=a+b2

Var[X]=(ba)212

MX(t)=etbetat(ba)(t0)

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)=12πσexp![(xμ)22σ2],xR

Parametry

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

E[X]=μ

Var[X]=σ2

MX(t)=exp!(μt+12σ2t2)

Suma niezależnych XiN(μi,σi2) jest również normalna:

iXiN!(μi,σi2)

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ą:

  1. zbuduj histogram,
  2. oblicz statystykę K–S Dn=supx|Fn(x)Φμ,σ(x)|,
  3. odrzucaj generator jeśli Dn>Dα,n dla wybranego poziomu α.

Dystrybucja Bernoulliego

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

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

Parametry

E[X]=p

Var[X]=p(1p)

MX(t)=1p+pet

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

i=1nXiBin(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 %:

p^±1.96p(1p)/n

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

Rozkład Kod dystr. <random> Parametry E[X] Var[X] Typ danych
Równomierny (dyskr.) std::uniform_int_distribution a,b a+b2 (ba+1)2112 całkowite
Normalny std::normal_distribution μ,σ μ σ2 zmiennoprzec.
Bernoulli std::bernoulli_distribution p p p(1p) 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:

xk+n=xk+m((xkuxk+1)A),n=624,m=397,okres=2199371106001,dmax=623(wymiar równomierności).

Spektralny test równoległości daje wynik rzędu 22018 – przy wielu zastosowaniach symulacyjnych uznaje się to za „praktycznie idealne”.

Zalety

Aspekt Wartość dodana Komentarz matematyczny
Okres 2199371 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=F1(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

  1. Trzeba rozumieć dwustopniowy model: generator + dystrybucja.
  2. 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ść.
  3. Koszt inicjalizacjistd::random_device może być wolny (blokuje podczas odczytu z /dev/urandom).
  4. 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:

xn+1=(axn+c)modm,

typowe stałe (glibc, MSVC):

a=1103515245,c=12345,m=231.

Okres ≤ m=231;(2.1109). 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

  1. Krótki okres generacji – przy prędkości 10⁸ liczb/s pełny cykl wyczerpuje się w ok. 21 s.
  2. Słabe własności spektralne – pojawiają się korelacje w przestrzeni 3D w symulacjach Monte Carlo.
  3. Niejednorodność implementacji – różne kompilatory używają odmiennych stałych.
  4. Brak wbudowanych rozkładów – konieczne ręczne przekształcenia (np. metoda Box–Mullera).
  5. Ł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 2199371 231
Równomierność dmax 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

Spis Treści

    Liczby losowe i generatory liczb losowych
    1. Liczby losowe
      1. Własności oczekiwane
      2. Prawdziwa losowość vs. pseudolosowość
    2. Generowanie liczb losowych
      1. Dystrybucje
      2. Inicjalizacja – właściwości ziarna
    3. Przykłady użycia (C++ 17)
      1. Liczba z przedziału [a,b]Z
      2. Rzut monetą – dystrybucja Bernoulliego
      3. Rzut sześciościenną kostką
      4. Generator silnych haseł
      5. Metody Monte Carlo
      6. RNG kryptograficzne (CSPRNG)
    4. Zastosowanie różnych dystrybucji
      1. Dystrybucja równomierna
      2. Dystrybucja normalna (Gaussa)
      3. Dystrybucja Bernoulliego
    5. Zalety i wady różnych metod
      1. std::random (C++11)
      2. rand() – klasyczny LCG
      3. Zestawienie porównawcze