RANDU

RANDU är en linjär kongruent pseudo-slumptalsgenerator som togs i bruk på 1960-talet. Det bestäms av återfallsrelationen :

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

var är udda . $V_{0}$

Pseudo-slumptal beräknas enligt följande:

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

Det är populärt att denna algoritm är en av de minst genomtänkta pseudo-slumptalsgeneratorerna som någonsin föreslagits, eftersom den inte klarar spektraltestet när antalet mätningar överstiger 2 [1] [2] .

Anledningen till att parametrarna för generatorn valdes var att, inom ramen för heltals 32-bitars maskinaritmetik, utförs modulo-operationer , i synnerhet multiplicering av ett godtyckligt tal med , effektivt. Samtidigt har detta val också en grundläggande nackdel. Tänk på följande uttryck (vi antar att alla operationer utförs 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))

varifrån vi utökar den kvadratiska faktorn får:

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

vilket i sin tur visar närvaron av ett linjärt samband (och därmed en fullständig korrelation ) mellan tre intilliggande element i sekvensen:

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

Som en konsekvens av korrelation är punkter i det tredimensionella rummet, vars koordinater erhålls med denna algoritm, belägna på ett relativt litet antal plan (i det givna exemplet på 15 plan). [3]

Exempel

Ett exempel på en pseudo-slumpmässig sekvens genererad av RANDU-algoritmen med ett initialt värde på : $V_{0}=1$

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

Citat

Själva namnet - RANDU (liknande "slumpmässigt" - "slumpmässigt" - Ungefär ed. ), kan orsaka skräck i ögonen och magkramper hos många datavetare! [fyra]

Originaltext (engelska)[ visaDölj]

… själva namnet RANDU räcker för att väcka bestörtning i ögon och magar hos många datavetare! [5]

En av oss minns att han en gång fick en grafisk bild av en "slumpmässig" sekvens, bestående av endast 11 plan. Som svar uppgav en programmeringskonsult i datacenter att slumptalsgeneratorn användes felaktigt: "Vi garanterar att varje nummer är slumpmässigt i sig, men vi garanterar inte att mer än ett av dem är slumpmässigt." Försök att förstå detta.

Originaltext (engelska)[ visaDölj]

En av oss minns att han producerade en "slumpmässig" plot med bara 11 plan och fick höra av sin datorcentrals programmeringskonsult att han hade missbrukat slumptalsgeneratorn: "Vi garanterar att varje nummer är slumpmässigt individuellt, men vi garanterar inte att mer än en av dem är slumpmässig." räkna ut. [6]

Anteckningar

↑ Peter Young. Randu: en dålig slumptalsgenerator . Fysik 115/242 (24 april 2013). Hämtad 11 september 2017. Arkiverad från originalet 22 december 2018. (obestämd)
↑ RANDU: den dåliga slumptalsgeneratorn . GitHub (16 februari 2016). Hämtad 11 september 2017. Arkiverad från originalet 31 juli 2016. (obestämd)
↑ George Marsaglia. Slumptal faller huvudsakligen i planen // Proc National Academy of Sciences: Journal. - September 1968. - V. 61 , nr 1 . - S. 25-28 .
↑ Donald Knuth . Kapitel 3.3. Spektralt kriterium // Konsten att programmera = Konsten att programmera. - 3:e uppl. - M. : "Williams" , 2007. - V. 2. Erhållna algoritmer. - S. 129-130. — 832 sid. — ISBN 5-8459-0081-6 (ryska) ISBN 0-201-89684-2 (engelska).
↑ Donald E. Knuth. Konsten att programmera. — 3:e uppl. - Boston: Addison-Wesley, 1998. - V. 2. Seminumeriska algoritmer.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numeriska recept i C: The Art of Scientific Computing. — 2:a uppl. - Cambridge University Press, 1992. - S. 277. - ISBN 0-521-43108-5 .

Ytterligare läsning

M. Maximov. Är slumptal slumpmässiga? - Tidskrift " Science and Life ", nr 10, 1986.

Länkar

RANDU slumptalsgenerator misslyckas med 3D+ spektraltester Arkiverad 19 november 2020 på Wayback Machine