RANDU

RANDU je generátor lineárních kongruentních pseudonáhodných čísel , který se začal používat v 60. letech 20. století. Je určena recidivou :

V_{j+1}\equiv (65539V_{j})\mod 2^{31}

kde je liché . $V_{0}$

Pseudonáhodná čísla se počítají takto:

X_{j}\equiv V_{j}/2^{31}

Všeobecně se má za to, že tento algoritmus je jedním z nejméně promyšlených generátorů pseudonáhodných čísel, které byly kdy navrženy, protože selže ve spektrálním testu , když počet měření překročí 2 [1] [2] .

Důvodem volby parametrů generátoru bylo, že v rámci celočíselné 32bitové strojní aritmetiky jsou efektivně prováděny modulo operace , zejména násobení libovolného čísla . Zároveň má tato volba i zásadní nedostatek. Uvažujme následující výraz (budeme předpokládat, že všechny operace se provádějí modulo ): $2^{{31}}$ $65539=2^{{16}}+3$ $2^{{31}}$

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

odkud, rozšířením kvadratického faktoru, dostaneme:

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

což zase ukazuje přítomnost lineárního vztahu (a tedy úplné korelace ) mezi třemi sousedními prvky sekvence:

{\displaystyle x_{k+2}=6x_{k+1}-9x_{k))

V důsledku korelace se body v trojrozměrném prostoru, jejichž souřadnice získáme tímto algoritmem, nacházejí na relativně malém počtu rovin (v daném příkladu na 15 rovinách). [3]

Příklad

Příklad pseudonáhodné sekvence generované algoritmem RANDU s počáteční hodnotou : $V_{0}=1$

jeden 65539 393225 1769499 7077969 26542323 95552217 334432395 1146624417 1722371299 14608041 ... 134633675 1893599841 1559961379 907304297 2141591611 388843697 238606867 79531577 477211307 jeden

Citáty

Už jeho samotný název – RANDU (podobně jako „random“ – „random“ – Approx. red. ), může u mnoha informatiků vyvolat zděšení v očích a žaludeční křeče! [čtyři]

Původní text (anglicky)[ zobrazitskrýt]

…jeho samotný název RANDU stačí k tomu, aby vyvolal zděšení v očích a žaludcích mnoha počítačových vědců! [5]

Jeden z nás vzpomíná, že kdysi dostal grafický obrázek „náhodné“ sekvence, skládající se pouze z 11 rovin. V reakci na to konzultant programování počítačového centra uvedl, že generátor náhodných čísel byl použit nesprávně: "Garantujeme, že každé číslo je náhodné samo o sobě, ale nezaručujeme, že náhodných je více než jedno." Zkuste to pochopit.

Původní text (anglicky)[ zobrazitskrýt]

Jeden z nás si vzpomíná, jak vytvořil „náhodný“ spiknutí pouze s 11 rovinami a programový konzultant jeho počítačového centra mu řekl, že zneužil generátor náhodných čísel: „Garantujeme, že každé číslo je náhodné jednotlivě, ale nezaručujeme, že více než jeden z nich je náhodný." vyřešit. [6]

Poznámky

↑ Peter Young. Randu: špatný generátor náhodných čísel . Fyzika 115/242 (24. dubna 2013). Získáno 11. září 2017. Archivováno z originálu 22. prosince 2018. (neurčitý)
↑ RANDU: špatný generátor náhodných čísel . GitHub (16. února 2016). Získáno 11. září 2017. Archivováno z originálu 31. července 2016. (neurčitý)
↑ George Marsaglia. Náhodná čísla padají hlavně v rovinách // Proc National Academy of Sciences: Journal. - září 1968. - V. 61 , č. 1 . - S. 25-28 .
↑ Donald Knuth . Kapitola 3.3. Spektrální kritérium // Umění programování = The Art of Computer Programming. - 3. vyd. - M. : "Williams" , 2007. - V. 2. Získané algoritmy. - S. 129-130. — 832 s. — ISBN 5-8459-0081-6 (ruština) ISBN 0-201-89684-2 (anglicky).
↑ Donald E. Knuth. Umění počítačového programování. — 3. vyd. - Boston: Addison-Wesley, 1998. - V. 2. Seminumerické algoritmy.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerické recepty v C: The Art of Scientific Computing. — 2. vyd. - Cambridge University Press, 1992. - S. 277. - ISBN 0-521-43108-5 .

Další čtení

M. Maksimov. Jsou náhodná čísla náhodná? - Časopis " Věda a život ", č. 10, 1986.

Odkazy

Generátor náhodných čísel RANDU selhal ve 3D+ spektrálních testech Archivováno 19. listopadu 2020 na Wayback Machine