13. Elementy Teorii Liczb, Generatory Liczb Pseudolosowych i Szum Biały

Generatory liczb (ciągów) pseudolosowych o rozkładzie jednostajnym oraz generatory pseudolosowych ciągów dwójkowych o rozkładzie dwupunktowym mogą być zrealizowane w sposób numeryczny, a generator pseudolosowych ciągów dwójkowych może być nawet zrealizowany sprzętowo.

Problem generacji liczb pseudolosowych związany jest z pojęciem ciała skończonego.

Rodzaje generatorów:

(1) Generator multiplikatywny jest to generator linowy zdefiniowany

$\bigwedge_{}^{}{n \in Z_{+}}$ w następujący sposób:

r₀ > 0

Oraz

r_n : = a r_n − 1(mod M).

(2) Generator mieszany jest generatorem liniowym, który $\bigwedge_{}^{}{n \in Z_{+}}$ ma postać:

r_n : = a r_n − 1 + b(mod M),

gdzie współczynnik b>0.

(3) Generator addytywny (uogólnionym generatorem Fibonacciego) nazywamy generator liniowy zdefiniowany $\bigwedge_{}^{}{n \in Z_{+}}$ za pomocą równań:

r₀ + b > 0

Oraz

$r_{n} : = \sum_{i = 0}^{k - 1}{a_{i}\ r_{n - k + 1} + \ b(mod\ M)},$

Gdzie współczynniki a₀, …,  a_k − 1, b ∈ {0,1}. A z kolei generator addytywny, który $\bigwedge_{}^{}{n \in Z_{+}}$ ma postać:

r₀ > 0

Oraz

r_n : = r_n − 1 +  r_n − 2(mod M),

Nazywamy generatorem Fibonacciego.

(4) Generatorem dwójkowym (binarnym) nazywamy generator liniowy zdefiniowany $\bigwedge_{}^{}{n \in Z_{+}}\ $za pomocą równań:

r₀ = 1

Oraz

$r_{n} : = \sum_{i = 0}^{k - 1}{a_{i}\ r_{n - k + 1}(mod\ 2)}\text{\ \ }$

Generatory tego rodzaju nazywane są też generatorami pseudolosowych ciągów dwójkowych, w skrócie generatorami PRBS (z ang. Pseudo-Random Binary Sequences).

(5) Wirówka mersenna’a (and. Mersenne Twister)

Mersenne Twister to algorytm generatora liczb pseudolosowych opracowany w 1997 przez Makoto Matsumoto i Takuji Nishimura. Generator jest szybki i dostarcza wysokiej jakości liczby pseudolosowe. Został zaprojektowany specjalnie dla naprawienia wielu wad, które znajdują się w starszych algorytmach.

Nazwa generatora pochodzi od tego, że na długość okresu wybierana jest liczba pierwsza Mersenne'a. Istnieją co najmniej dwa warianty algorytmu, które różnią się jedynie wielkością użytych liczb pierwszych Mersenne'a.

Twierdzenie o generatorze multiplikatywnym:
Jeżeli dla generatora multiplikatywnego

r₀ > 0

Oraz

r_n : = a r_n − 1(mod M)

moduł

M = 2^m

Oraz m ≥ 3, to maksymalny jego okres

N_max = 2^m − 2

można osiągnąć dla nieparzystych wartości r₀, gdy

a ≡ 3(mod 8)

lub

a ≡ 5(mod 8)

Twierdzenie o generatorze mieszanym:

Jeżeli dla generatora mieszanego

r_n = r_n − 1 + b(mod M)

Liczby b i M są względnie pierwsze dla każdego czynnika pierwszego p modułu M

a ≡ 1(mod p)

Oraz

a ≡ 1(mod 4),

Gdy 4 jest dzielnikiem M, to ma on maksymalny okres

N_max = M.

Twierdzenie o generatorze Fibonacciego:

Jeżeli dla generatora Fibonacciego

r₀ > 0

oraz

r_n = r_n − 1 + r_n − 2(mod M),

moduł

M = 2^m,

to maksymalny jego okres

N_max = 3 * 2^m − 1

I nie zależy od wyboru r₀ i r₁.

W grach komputerowych czy algorytmach probabilistycznych (takich jak np.całkowanie Monte Carlo) potrzebne jest jedynie źródło wartości o cechach przybliżonych do liczb prawdziwie losowych, chociaż jakość losowości może być decydująca dla dokładności obliczeń. Dlatego przy zastosowaniu każdego nowego generatora do celów obliczeń numerycznych należy sprawdzić jego własności statystyczne.