RANDU

Pokud generovaná čísla bereme po trojicích jako souřadnice bodů, padnou do patnácti rovin, jak ukazuje tento trojrozměrný graf pro prvních sto tisíc hodnot

RANDU je lineární kongruentní generátor pseudonáhodných čísel Parkova-Millerova typu, který byl používán od šedesátých let dvacátého století. Je definován rekurentní rovnicí

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

kde $\scriptstyle V_{0}$ je liché. Generuje pseudonáhodná celá čísla $\scriptstyle V_{j}$ v intervalu $[1,2^{31}-1]$.

RANDU je považován za jeden z nejhorších navržených a používaných generátorů pseudonáhodných čísel. Neprojde spektrálním testem pro dimenzi větší než 2, výsledkem jsou jen lichá čísla. Přesto se používal poměrně dlouho a na „náhodnosti“ jeho výstupu je založena řada vědeckých článků z počátku sedmdesátých let, kdy byl obzvlášť v oblibě.

Motivací pro volbu parametrů bylo, že na běžných počítačích lze velice rychle provést operace modulo 2³¹ a násobení číslem $65539=2^{16}+2^{1}+1$. První z nich lze realizovat vynulováním dvou nejvýznamnějších bitů 32bitového registru a druhou z nich lze realizovat jen pomocí sčítání a dvou bitových posunů, tedy aniž by bylo potřeba provádět obecné násobení.

Rychlým výpočtem ovšem výhody končí, neboť zvolené hodnoty vedou k velmi degenerované náhodnosti, jak vidíme z následujícího rozepsání rekurzivního vztahu (všechny následující výpočty probíhají modulo 2³¹):

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

z čehož umocněním máme

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

kde zjednodušení plyne z toho, že $2^{32}\mod 2^{16}=0$. Vidíme tedy, jak prostý je vztah mezi třemi po sobě následujícími hodnotami:

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

Nedostatečnou náhodost generovaných čísel lze ukázat i obrázkem. Jak totiž ukázal v roce 1968 George Marsaglia, tak pokud generovaná čísla budeme brát po trojicích jako souřadnice bodů eukleidovského prostoru, pak všechny takto získané body padnou do pouhých patnácti rovin.

Reference

V tomto článku byl použit překlad textu z článku RANDU na anglické Wikipedii.