RANDU

RANDU er en lineær kongruent pseudo-tilfældig talgenerator , der kom i brug i 1960'erne. Det bestemmes af gentagelsesforholdet :

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

hvor er mærkeligt . $V_{0}$

Pseudo-tilfældige tal beregnes som følger:

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

Det er populært antaget, at denne algoritme er en af de mindst gennemtænkte pseudo-tilfældige tal-generatorer, der nogensinde er foreslået, da den fejler spektraltesten, når antallet af målinger overstiger 2 [1] [2] .

Grunden til at vælge parametrene for generatoren var, at inden for rammerne af heltal 32-bit maskinaritmetik udføres modulo-operationer , især multiplikation af et vilkårligt tal med , effektivt. Samtidig har dette valg også en grundlæggende ulempe. Overvej følgende udtryk (vi antager, at alle operationer udføres 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))

hvorfra vi udvider den kvadratiske faktor får:

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

som igen viser tilstedeværelsen af et lineært forhold (og dermed en fuldstændig korrelation ) mellem tre tilstødende elementer i sekvensen:

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

Som en konsekvens af korrelation er punkter i det tredimensionelle rum, hvis koordinater opnås af denne algoritme, placeret på et relativt lille antal planer (i det givne eksempel på 15 planer). [3]

Eksempel

Et eksempel på en pseudo-tilfældig sekvens genereret af RANDU-algoritmen med en startværdi på : $V_{0}=1$

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

Citater

Selve dens navn - RANDU (ligner "tilfældig" - "tilfældig" - Ca. red. ), kan forårsage forskrækkelse i øjnene og mavekramper hos mange dataloger! [fire]

Originaltekst (engelsk)[ Visskjule]

… selve navnet RANDU er nok til at bringe forfærdelse i øjnene og maven på mange dataloger! [5]

En af os husker, at han engang modtog et grafisk billede af en "tilfældig" sekvens, der kun bestod af 11 fly. Som svar udtalte en programmeringskonsulent i computercentret, at tilfældig talgeneratoren blev brugt forkert: "Vi garanterer, at hvert tal er tilfældigt i sig selv, men vi garanterer ikke, at mere end et af dem er tilfældigt." Prøv at forstå dette.

Originaltekst (engelsk)[ Visskjule]

En af os husker, at han lavede et "tilfældigt" plot med kun 11 fly og fik at vide af sit computercenters programmeringskonsulent, at han havde misbrugt tilfældig talgeneratoren: "Vi garanterer, at hvert tal er tilfældigt individuelt, men vi garanterer ikke, at mere end én af dem er tilfældig." finde ud af. [6]

Noter

↑ Peter Young. Randu: en dårlig tilfældig talgenerator . Fysik 115/242 (24. april 2013). Hentet 11. september 2017. Arkiveret fra originalen 22. december 2018. (ubestemt)
↑ RANDU: den dårlige tilfældige talgenerator . GitHub (16. februar 2016). Hentet 11. september 2017. Arkiveret fra originalen 31. juli 2016. (ubestemt)
↑ George Marsaglia. Tilfældige tal falder hovedsageligt i flyene // Proc National Academy of Sciences: Journal. - september 1968. - V. 61 , nr. 1 . - S. 25-28 .
↑ Donald Knuth . Kapitel 3.3. Spektralt kriterium // Kunsten at programmere = Kunsten at programmere computer. - 3. udg. - M. : "Williams" , 2007. - V. 2. Opnåede algoritmer. - S. 129-130. — 832 s. — ISBN 5-8459-0081-6 (russisk) ISBN 0-201-89684-2 (engelsk).
↑ Donald E. Knuth. Kunsten at programmere computer. — 3. udg. - Boston: Addison-Wesley, 1998. - V. 2. Seminumeriske algoritmer.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numeriske opskrifter i C: The Art of Scientific Computing. — 2. udg. - Cambridge University Press, 1992. - S. 277. - ISBN 0-521-43108-5 .

Yderligere læsning

M. Maksimov. Er tilfældige tal tilfældige? - Tidsskrift " Science and Life ", nr. 10, 1986.

RANDU

Eksempel

Citater

Noter

Yderligere læsning

Links