RANDU

RANDU este un generator liniar de numere pseudo-aleatorie congruent care a intrat în uz în anii 1960. Este determinată de relația de recurență :

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

unde este ciudat . $V_{0}$

Numerele pseudo-aleatorie se calculează după cum urmează:

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

Se crede popular că acest algoritm este unul dintre generatoarele de numere pseudoaleatoare cel mai puțin bine gândite propuse vreodată, deoarece eșuează testul spectral atunci când numărul de măsurători depășește 2 [1] [2] .

Motivul pentru alegerea parametrilor generatorului a fost că, în cadrul aritmeticii mașinii întregi pe 32 de biți, operațiile modulo , în special, înmulțirea unui număr arbitrar cu , sunt efectuate eficient. În același timp, această alegere are și un dezavantaj fundamental. Luați în considerare următoarea expresie (vom presupune că toate operațiile sunt efectuate modulo ): $2^{{31}}$ $65539=2^{{16}}+3$ $2^{{31}}$

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

de unde, extinzând factorul patratic, obținem:

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

care, la rândul său, arată prezența unei relații liniare (și, prin urmare, o corelație completă ) între trei elemente adiacente ale secvenței:

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

Ca o consecință a corelației, punctele din spațiul tridimensional, ale căror coordonate sunt obținute prin acest algoritm, sunt situate pe un număr relativ mic de plane (în exemplul dat, pe 15 plane). [3]

Exemplu

Un exemplu de secvență pseudo-aleatoare generată de algoritmul RANDU cu o valoare inițială de : $V_{0}=1$

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

Citate

Însuși numele său - RANDU (asemănător cu „aleatoriu” - „aleatoriu” - Aprox. ed. ), poate provoca frică în ochi și crampe de stomac la mulți informaticieni! [patru]

Text original (engleză)[ arataascunde]

… chiar numele său RANDU este suficient pentru a aduce consternare în ochii și stomacurile multor informaticieni! [5]

Unul dintre noi își amintește că a primit odată o imagine grafică a unei secvențe „aleatorie”, formată din doar 11 avioane. Ca răspuns, un consultant de programare a unui centru de calculatoare a declarat că generatorul de numere aleatorii a fost folosit incorect: „Garantăm că fiecare număr este aleatoriu în sine, dar nu garantăm că mai mult de unul dintre ele este aleatoriu”. Încercați să înțelegeți asta.

Text original (engleză)[ arataascunde]

Unul dintre noi își amintește că a produs un complot „aleatoriu” cu doar 11 avioane și i s-a spus de către consultantul de programare al centrului său de calcul că a folosit greșit generatorul de numere aleatorii: „Garantăm că fiecare număr este aleatoriu individual, dar nu garantăm că mai multe dintre ele sunt aleatorii.” a-şi da seama. [6]

Note

↑ Peter Young. Randu: un generator de numere aleatoare prost . Fizica 115/242 (24 aprilie 2013). Preluat la 11 septembrie 2017. Arhivat din original la 22 decembrie 2018. (nedefinit)
↑ RANDU: generatorul prost de numere aleatoare . GitHub (16 februarie 2016). Consultat la 11 septembrie 2017. Arhivat din original la 31 iulie 2016. (nedefinit)
↑ George Marsaglia. Numerele aleatorii cad în principal în planuri // Proc National Academy of Sciences: Journal. - septembrie 1968. - V. 61 , nr 1 . - S. 25-28 .
↑ Donald Knuth . Capitolul 3.3. Criteriu spectral // Arta programării = The Art of Computer Programming. - Ed. a 3-a. - M. : „Williams” , 2007. - V. 2. Algoritmi obținuți. - S. 129-130. — 832 p. — ISBN 5-8459-0081-6 (rusă) ISBN 0-201-89684-2 (engleză).
↑ Donald E. Knuth. Arta programarii pe computer. — Ed. a 3-a. - Boston: Addison-Wesley, 1998. - V. 2. Algoritmi semimerici.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Rețete numerice în C: Arta calculului științific. — Ed. a II-a. - Cambridge University Press, 1992. - P. 277. - ISBN 0-521-43108-5 .

Lectură suplimentară

M. Maksimov. Numerele aleatoare sunt aleatorii? - Jurnalul „ Știință și viață ”, nr. 10, 1986.

Link -uri

Generatorul de numere aleatoare RANDU eșuează testele spectrale 3D+ Arhivat 19 noiembrie 2020 la Wayback Machine