srand i rand vs – generatory liczb pseudolosowych i statystyczna jakość losu

Porównanie generatorów liczb pseudolosowych: tradycyjne funkcje C (srand, rand) a biblioteka <random> w C++

Podsumowanie kluczowych ustaleń

Tradycyjne funkcje srand() i rand() z języka C oraz współczesna biblioteka <random> w C++ reprezentują fundamentalnie różne podejścia do generowania liczb pseudolosowych. Podczas gdy mechanizmy C opierają się na prostych generatorach kongruencyjnych o ograniczonych właściwościach statystycznych, biblioteka C++ oferuje zestaw zaawansowanych generatorów i dystrybucji zaprojektowanych do spełnienia wymogów stochastycznych w aplikacjach naukowych i inżynieryjnych. Analiza jakości statystycznej ujawnia znaczącą przewagę <random>, szczególnie w kontekście jednorodności rozkładu, długości okresu i odporności na korelacje sekwencyjne. Właściwości te potwierdzają baterie testów statystycznych takie jak TestU01 i PractRand, gdzie generatory z biblioteki standardowej C++ konsekwentnie osiągają lepsze wyniki w porównaniu z klasyczną implementacją rand().

Historyczne generatory w języku C

Mechanizm działania rand() i srand()
Funkcje rand() i srand() stanowią historyczne API do generowania liczb pseudolosowych w C, zdefiniowane w nagłówku stdlib.h. Jak wynika z analizy implementacji, rand() zwraca liczbę całkowitą z zakresu [0, RAND_MAX], gdzie typowa wartość RAND_MAX to 32767 (2¹⁵-1) lub 2147483647 (2³¹-1) w nowszych implementacjach. Kluczową cechą jest deterministyczna natura generatora – sekwencja wartości jest w pełni określona przez ziarno (ang. seed) ustawiane za pomocą srand(unsigned int). Brak inicjalizacji ziarna skutkuje domyślnym użyciem wartości 1, co prowadzi do identycznych sekwencji między uruchomieniami programu.

Problemy jakościowe i statystyczne
Główne ograniczenia tradycyjnego generatora obejmują:

• Krótki okres – podstawowe implementacje wykorzystują liniowy generator kongruencyjny (LCG) postaci Xₙ₊₁ = (a·Xₙ + c) mod m. Dla typowych parametrów (np. a=1103515245, c=12345, m=2³¹ w glibc) okres wynosi zaledwie 2³¹ ≈ 2.1e9 stanów;
• Niejednorodność rozkładu – operacja modulo wprowadza istotne obciążenie przy mapowaniu na mniejsze zakresy. Przykładowo, generowanie liczb z przedziału [0,5] poprzez rand() % 6 powoduje nierównomierny rozkład, gdyż 6 nie jest dzielnikiem RAND_MAX+1;
• Niska wymiarowość – punkty w przestrzeni wielowymiarowej wykazują silne korelacje i struktury sieciowe. W praktyce oznacza to, że współrzędne generowanych punktów skupiają się na hiperpłaszczyznach, co dyskwalifikuje ten generator w symulacjach Monte Carlo;
• Przewidywalność – algorytm jest podatny na kryptoanalizę – obserwacja około 3-4 kolejnych wartości pozwala odtworzyć całą sekwencję.

Techniki poprawy jakości
W odpowiedzi na te ograniczenia opracowano metody takie jak próbkowanie z odrzuceniem (ang. rejection sampling). Algorytm ten generuje wartości z przedziału [0, n-1] poprzez odrzucanie wyników z „nadmiarowego” fragmentu zakresu:

int randRange(int n) {
    int limit = RAND_MAX - (RAND_MAX % n);
    int r;
    do {
        r = rand();
    } while (r >= limit);
    return r % n;
}

Technika ta eliminuje błąd systematyczny kosztem zmiennej liczby wywołań rand(). Mimo to, fundamentalne ograniczenia LCG pozostają nierozwiązane.

Współczesne generatory w C++

Architektura biblioteki <random>
Biblioteka wprowadzona w standardzie C++11 dostarcza modularny system generacji liczb pseudolosowych, oparty na trzech komponentach:

1. Silniki (ang. engines) – implementują podstawowe generatory.

• std::mt19937: Mersenne Twister o okresie 2¹⁹⁹³⁷-1 i 623-wymiarowej równomierności,
• std::mt19937_64: 64-bitowa wersja MT,
• std::linear_congruential_engine: LCG z konfigurowalnymi parametrami,
• std::subtract_with_carry: generator z przeniesieniem (LFG).

1. Adaptatory (ang. adaptors) – modyfikują wyjście silników (np. discard_block).
2. Dystrybucje (ang. distributions) – mapują wyjście silnika na pożądany rozkład.

Zalety jakościowe

• Długi okres – mt19937 gwarantuje okres 2¹⁹⁹³⁷-1 (≈4.3·10⁶⁰⁰¹), co eliminuje ryzyko powtórzeń w praktycznych zastosowaniach;
• Wysoka wymiarowość – sekwencje wykazują jednorodność w przestrzeniach do 623 wymiarów;
• Brak korelacji liniowych – zaawansowana algebra macierzowa minimalizuje wzorce w danych wyjściowych;
• Reprodukowalność – kontrola nad ziarnem pozwala na powtarzalność eksperymentów.

Prawidłowe użycie
Przykład inicjalizacji generatora i wykorzystania dystrybucji:

#include <random>
std::random_device rd; // Źródło entropii sprzętowej
std::mt19937 gen(rd()); // Inicjalizacja ziarnem
std::uniform_int_distribution<> dist(1, 6); // Dystrybucja jednostajna
int dice_roll = dist(gen); // Generacja wartości

Kluczowa jest tu rola std::random_device, które pozyskuje entropię z systemu operacyjnego, zapewniając nieprzewidywalność.

Analiza jakości statystycznej

Metodologie testowania
Standardem branżowym są baterie testów statystycznych, które weryfikują hipotezę losowości sekwencji:

• TestU01 – obejmuje testy SmallCrush (10 testów), Crush (96 testów) i BigCrush (106 testów). Wykrywa niejednorodność, korelacje i nieliniowe zależności;
• PractRand – testuje strumienie binarne, szczególnie czuły na niską entropię;
• Diehard – historyczna bateria 15 testów, obecnie rozszerzona do Dieharder.

Wyniki testów dla rand()
Generator LCG używany w rand() systematycznie nie przechodzi zaawansowanych testów:

• w TestU01: niepowodzenia w testach Gap, MaxOft i Permutation w ramach Crush,
• w PractRand: wykrywalne wzorce przy >2^35 bajtach danych,
• wspólne problemy: niejednorodność dystrybucji, korelacja bitów niższego rzędu, powtarzalne sekwencje.

Wyniki dla <random>

• std::mt19937: przechodzi wszystkie testy SmallCrush i Crush. W BigCrush obserwuje się marginalne niepowodzenia w 2 z 106 testów, co nie dyskwalifikuje go w zastosowaniach niekryptograficznych,
• std::mt19937_64: lepsza wydajność w testach 64-bitowych,
• std::random_device: generuje liczby oparte na entropii sprzętowej, przechodząc wszystkie testy statystyczne (kryptograficznie bezpieczne w poprawnych implementacjach).

Praktyczne porównanie

Zastosowania i rekomendacje

Dopuszczalne użycie rand()

• inicjalizacja niekrytycznych zmiennych,
• edukacja podstaw programowania,
• aplikacje bez wymagań statystycznych.

Scenariusze wymagające <random>

• symulacje naukowe (Monte Carlo),
• algorytmy uczenia maszynowego,
• generacja światów w grach (proceduralna),
• systemy kolejkowania (symulacje zdarzeń).

Najlepsze praktyki

1. Unikaj rand() w nowym kodzie C++ na rzecz <random>.
2. Do inicjalizacji używaj std::random_device.
3. Wybierz silnik odpowiedni do zadania:

• std::mt19937 dla ogólnych zastosowań,
• std::ranlux48 dla lepszej jakości (kosztem wydajności).

1. Zawsze używaj dystrybucji zamiast operacji modulo:
   // Zamiast: int value = rand() % 100; std::uniform_int_distribution<int> dist(0, 99);
2. Testuj generatory w aplikacjach wrażliwych (TestU01/PractRand).

Wnioski

Podczas gdy historyczne generatory rand() i srand() spełniają podstawowe wymagania w aplikacjach o niskich oczekiwaniach statystycznych, ich fundamentalne ograniczenia czynią je nieodpowiednimi do zaawansowanych zastosowań obliczeniowych. Współczesna biblioteka <random> w C++ oferuje nie tylko dłuższe okresy i lepszą jakość stochastyczną, ale również modularną architekturę umożliwiającą dobór generatora do specyfiki problemu. Potwierdzenie jakości przez standaryzowane baterie testów statystycznych stanowi mocny argument za preferowaniem tego podejścia w nowych implementacjach. Dla twórców systemów krytycznych rekomenduje się dodatkową walidację z użyciem TestU01 lub PractRand, szczególnie przy długotrwałych symulacjach.