447 2

447

11.4. Liczby pseudolosowe

_ł^_jR!j_ej^,ir7e arytmetycznym maszyny. Tak otrzymywane liczby nie są, ściśle mówiąc, losowe. J^jpulańitćjsze metody generowania dają liczby pseudolosowe spełniające pewne pomysłowo zbudowane testy statystyczne ich losowości równie dobrze, iak ..prawdziwe*' liczby losowe.

^ 'fcjezby pseudolosowe tworzy się najczęściej za pomocą tzw. generatorów mieszanych. Miech P będzie dużą liczbą całkowitą i niech x₀, X i fi będą trzema dodatnimi liczbami całkowitymi mniejszymi od P. Liczby całkowite x₃, ... \0^x„<P) tworzy się reku-^ńcyjnie zgodnie z wzorem

(j 1.4.1)    x._{+ 1}=ix.+#i(modP).

Inaczej mówiąc, , jest resztą z dzielenia Xx_H + ft przez P. (Z reguły liczby /. fi i P są tak proste, aby x_nĄ, można było utworzyć za pomocą szybszych operacji, np. przesunięć). Ciąg {R_n}, gdzie R_n-x_r!P, nazywa się ciągiem liczb pseudolosowych o rozkładzie prostokątnym w przedziale [0, IJ.

Można wykazać, że jeśli P=2' (co jest naturalne w maszynie dwójkowej), fi jest nieparzyste, a X daje resztę 1 przy dzieleniu przez 4, to okres ciągu jest równy 2\ Liczne badania teoretyczne i doświadczalne dały dobre wyniki, np.- dla P= 2³⁵.

A=2⁴ + B,    \S^A^24,    5=1,5,9. p = l.

Dokładniejsze wiadomości podaje Jansson [150].

„Prawdziwe” liczby losowe i liczby pseudolosowe generowane za pomocą wzoru (11.4.1) różnią się w istotny, ważny w praktyce sposób. Nie. można uważać, że cyfry liczb pseudo-losvmch są niezależnymi cyframi losowymi. Użycie (jak w przykładzie 11.2.2) cyfr liczby pseudolosowej do utworzenia kilku krótszych liczb może być ryzykowne. Istnieją inne (bardziej czasochłonne) sposoby generowania liczb pseudolosowych. usuwające to ryzyko.

Gdy bada się (np. w ciągu liczb pseudolosowych generowanych z (11.4.1) dla p=0, J^>=2 ) ciąg cyfr na pewnej pozycji. np. iMej od lewej strony, wtedy okazuje się. Ze im większe J^c"t c, tym krótszy jest okres. Ostatnia cyfra, jeśli x_a i X są nieparzyste, jest zawsze równa 1!

Pytanie przeglądowe

tojest generator mieszany? Jaka jest istotna różnica między liczbami otrzymywanymi z tego generatora i „prawdziwymi” liczbami losowymi?

Zadania

1. Jeśli w (11.4.1) jest fi— 0, to znów* i się o generatorze muliypiikaływnym. Można wy-"dzać, żę jeśli *₀ jest nieparzyste, P = 2' 0^3) i że3 lub As5 (mod 8), to okres genero-'^ego ciągu jest równy 2^r~²; jest to maksymalny okres dla takiego generatora. W pew-zastosowaniach generator multyplikatywny jest lepszy (nieco szybszy) od mieszanego .jZOb. jednak uwagi na końcu § li.4). W szczególności w wielu realizacjach Fortranu brak ^gftalizaeji nadmiaru całkowitego można wykorzystać po to, aby napisać efektywny pod-