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. +more 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 231 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 231):

: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 \cdot2^{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

Kategorie:Generátory pseudonáhodných čísel