RANDU

RANDU  on lineaarinen kongruentti pseudosatunnaislukugeneraattori , joka otettiin käyttöön 1960-luvulla. Sen määrää toistuvuussuhde :

missä on outoa .

Pseudosatunnaisluvut lasketaan seuraavasti:

Yleisesti uskotaan, että tämä algoritmi on yksi vähiten harkituista näennäissatunnaislukugeneraattoreista, joita on koskaan ehdotettu, koska se epäonnistuu spektritestissä, kun mittausten määrä ylittää 2 [1] [2] .

Syynä generaattorin parametrien valinnalle oli se, että kokonaislukujen 32-bittisen konearitmeetiikan puitteissa modulo-operaatiot , erityisesti mielivaltaisen luvun kertominen luvulla , suoritetaan tehokkaasti. Samalla tällä valinnalla on myös perustavanlaatuinen haittapuoli. Harkitse seuraavaa lauseketta (oletamme, että kaikki toiminnot suoritetaan modulo ):

mistä laajentamalla neliötekijää saamme:

joka puolestaan ​​osoittaa lineaarisen suhteen (ja siten täydellisen korrelaation ) olemassaolon sekvenssin kolmen vierekkäisen elementin välillä:

Korrelaation seurauksena kolmiulotteisen avaruuden pisteet, joiden koordinaatit saadaan tällä algoritmilla, sijaitsevat suhteellisen pienellä määrällä tasoja (annetussa esimerkissä 15 tasossa). [3]

Esimerkki

Esimerkki RANDU-algoritmin luomasta näennäissatunnaisesta sekvenssistä, jonka alkuarvo on :

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

Lainaukset

Sen nimi - RANDU (samanlainen kuin "satunnainen" - "satunnainen" - noin toim. ) voi aiheuttaa säikähdystä silmissä ja vatsakramppeja monille tietotekniikan tutkijoille! [neljä]

Alkuperäinen teksti  (englanniksi)[ näytäpiilottaa]

…sen nimensä RANDU riittää saamaan tyrmistyksen monien tietojenkäsittelytieteilijöiden silmiin ja vatsaan! [5]

Yksi meistä muistaa, että hän sai kerran graafisen kuvan "satunnaisesta" sekvenssistä, joka koostui vain 11 tasosta. Vastauksena tietokonekeskuksen ohjelmointikonsultti totesi, että satunnaislukugeneraattoria on käytetty väärin: "Takaamme, että jokainen numero on sinänsä satunnainen, mutta emme takaa, että useampi kuin yksi niistä on satunnainen." Yritä ymmärtää tämä.

Alkuperäinen teksti  (englanniksi)[ näytäpiilottaa]

Eräs meistä muistaa tehneensä "satunnaisen" juonen, jossa oli vain 11 konetta, ja hänen tietokonekeskuksensa ohjelmointikonsultti kertoi hänelle, että hän oli käyttänyt väärin satunnaislukugeneraattoria: "Takaamme, että jokainen numero on satunnainen erikseen, mutta emme takaa, että useampi kuin yksi niistä on satunnainen." selvittää. [6]

Muistiinpanot

  1. ↑ Peter Young. Randu: huono satunnaislukugeneraattori . Fysiikka 115/242 (24. huhtikuuta 2013). Haettu 11. syyskuuta 2017. Arkistoitu alkuperäisestä 22. joulukuuta 2018.
  2. ↑ RANDU: huono satunnaislukugeneraattori . GitHub (16. helmikuuta 2016). Haettu 11. syyskuuta 2017. Arkistoitu alkuperäisestä 31. heinäkuuta 2016.
  3. ↑ George Marsaglia. Satunnaisluvut putoavat pääasiassa tasoissa  // Proc National Academy of Sciences: Journal. - Syyskuu 1968. - V. 61 , nro 1 . - S. 25-28 .
  4. ↑ Donald Knuth . Luku 3.3. Spektrikriteeri // Ohjelmoinnin taito = The Art of Computer Programming. - 3. painos - M. : "Williams" , 2007. - V. 2. Saadut algoritmit. - S. 129-130. — 832 s. — ISBN 5-8459-0081-6 (venäjä) ISBN 0-201-89684-2 (englanniksi).
  5. ↑ Donald E. Knuth. Tietokoneohjelmoinnin taide. – 3. painos - Boston: Addison-Wesley, 1998. - V. 2. Seminumerical Algorithms.
  6. ↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numeeriset reseptit julkaisussa C: Tieteellisen laskennan taide. – 2. painos - Cambridge University Press, 1992. - S. 277. - ISBN 0-521-43108-5 .

Lue lisää

Linkit