RANDU

Trójwymiarowy wykres 100 000 wartości wygenerowany za pomocą RANDU. Każdy punkt reprezentuje 3 kolejne wartości pseudolosowe. Wyraźnie widać, że punkty leżą na 15 dwuwymiarowych płaszczyznach .

RANDU to liniowy kongruencyjny generator liczb pseudolosowych (LCG) typu Parka-Millera , który był używany głównie w latach 60. i 70. XX wieku. Jest to określone przez powtarzalność :

${\ Displaystyle V_ {j + 1} = 65539 \ cdot V_ {j} \ {\ bmod {\,}} 2 ^ {31} \,}$

z początkowym numerem $jako$ liczbą nieparzystą . Generuje pseudolosowe $,$ całkowite , $.$ są równomiernie rozłożone w przedziale [1, 2 ³¹ - 1] w praktycznych zastosowaniach są często odwzorowywane na pseudolosowe wymierne w przedziale (0, 1) , według wzoru:

${\ Displaystyle X_ {j} = {\ Frac {V_ {j}} {2 ^ {31}}}}$ .

IBM RANDU jest powszechnie uważany za jeden z najbardziej nieprzemyślanych generatorów liczb losowych, jakie kiedykolwiek zaprojektowano, i został opisany jako „naprawdę okropny” przez Donalda Knutha . Źle przechodzi test spektralny dla wymiarów większych niż 2, jak zostanie to pokazane poniżej.

Powodem wybrania tych konkretnych wartości mnożnika i modułu było to, że przy 32-bitowym rozmiarze słowa całkowitego arytmetyka mod 2 ³¹ i ${\ Displaystyle 65539}$${\ Displaystyle ( ( Obliczenia {\text{ie, }}2^{16}+3)}$ można było wykonać szybko, używając sprzętowych operatorów bitowych , ale wartości wybrano dla wygody obliczeniowej, a nie dla jakości statystycznej.

Problemy z mnożnikiem i modułem

Dla dowolnego generatora kongruencji liniowej o module m używanym do generowania punktów w n - wymiarowej przestrzeni, punkty mieszczą się w nie więcej niż ${\ Displaystyle (n! \ razy m) ^ {1/n} }$ równoległe hiperpłaszczyzny. Wskazuje to, że niskomodułowe LCG nie nadają się do wielowymiarowej symulacji Monte Carlo . Dla m = 2^31 i n = 3 LCG może mieć do 2344 płaszczyzn, teoretyczne maksimum. W tym samym artykule Marsaglii udowodniono, że znacznie węższa górna granica jest sumą wartości bezwzględnych wszystkich współczynników hiperpłaszczyzn w postaci standardowej. To znaczy, jeśli hiperpłaszczyzny mają postać Ax1 + Bx2 + Cx3 = jakaś liczba całkowita, taka jak 0, 1, 2 itd., to maksymalna liczba płaszczyzn to |A|+|B|+|C|.

Teraz zbadamy wartości mnożnika 65539 i modułu 2 ³¹ wybranych dla RANDU. Rozważmy następujące obliczenie, w którym należy wziąć każdy wyraz mod 2 ³¹ . Zacznij od zapisania relacji rekurencyjnej jako:

${\ Displaystyle x_ {k + 2} = (2 ^ {16} + 3) x_ {k + 1} =(2^{16}+3)^{2}x_{k}\,}$

co staje się po rozwinięciu współczynnika kwadratowego:

${\ Displaystyle x_ {k + 2} = (2 ^ {32} + 6\cdot 2^{16}+9)x_{k}=[6\cdot (2^{16}+3)-9]x_{k}\,} ponieważ$

2 32 ^mod 2 ³¹ = 0

i pozwala nam pokazać korelację między trzema punktami jako:

${\ Displaystyle x_ {k + 2} = 6x_ {k + 1} -9x_ {k} \,}$

Sumując bezwzględne wartości współczynników, otrzymujemy nie więcej niż 16 płaszczyzn w 3D, stając się tylko 15 płaszczyznami po bliższym przyjrzeniu się, jak pokazano na powyższym schemacie. Nawet jak na standardy LCG pokazuje to, że RANDU jest okropne: użycie RANDU do próbkowania sześcianu jednostkowego pobierze tylko 15 równoległych płaszczyzn, nawet nie zbliżając się do górnej granicy 2344 płaszczyzn.

W wyniku szerokiego wykorzystania RANDU we wczesnych latach 70. wiele wyników z tego czasu można uznać za podejrzane. To niewłaściwe zachowanie zostało wykryte już w 1963 roku na komputerze 36-bitowym i starannie ponownie zaimplementowane w 32-bitowym systemie IBM System/360 . Uważano, że został szeroko oczyszczony na początku lat 90., ale nadal istniały kompilatory FORTRAN, które używały go dopiero w 1999 roku.

Przykładowe wyjście

Początek okresu wyjściowego RANDU dla początkowego ziarna to: ${\ Displaystyle V_ {0} = 1}$

1, 65539, 393225, 1769499, 7077969, 26542323, … (sekwencja A096555 w OEIS )