Ero sivun ”Näennäissatunnaislukugeneraattori” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
linkki ei toimi |
|||
Rivi 9:
jollain sopivalla [[funktio]]lla.
x<sub>n+1</sub> = f(x<sub>n</sub>)
Ensimmäinen luku on valittava, ja sitä sanotaan '''siemeneksi'''. Mikäli satunnaisluvuksi tulee sama kuin siemenestä, koko kierros alkaa identtisenä alusta.
Tunnettu näennäissatunnaislukugeneraattori on [[Linear Congruential Generator|LCG]], jossa f(x)=(a*x+b) mod c. Käytännössä c on yleensä kahden potenssi, koska se mahdollistaa hitaan mod-operaation korvaamisen yksinkertaisella binäärisellä AND-operaatiolla. Kun prosessori pystyy työskentelemään log<sub>2</sub>(c) -bittisillä kokonaisluvuilla, myös AND-operaatio voidaan ohittaa koska c:n ylittävä osa luvusta "leikkaantuu" pois kokonaislukuylivuodon avulla.
''Numerical recipes in C'' mainitsee LCG:n jossa a=1664525, b=1013904223 ja c=2<sup>32</sup>. Tämän generaattorin jakso on 2<sup>32</sup>.
Vaikka LCG on helppo toteuttaa, sen viat ovat ilmeisiä esimerkiksi statistisissa testeissä. LCG häviää myös nopeudessa kehittyneemmille generaattoreille jotka eivät käytä kertolaskua. LCG voi kuitenkin olla riittävä käyttötarkoituksiin jotka eivät vaadi korkeatasoista "satunnaisuutta", esimerkiksi videopeleille.
Satunnaislukugeneraattori, joka yksinkertaisesti ajaa funktion edelliselle generoidulle luvulle, omaa jakson jonka pituus on maksimissaan yhtä kuin sallittujen lukujen lukumäärä. Syntymäpäiväparadoksin vuoksi täyden jakson omaavan generaattorin statistinen virheellisyys alkaa kuitenkin viimeistään näkyä kun generoitujen lukujen lukumäärä on kutakuinkin sallittujen lukujen lukumäärän neliöjuuri. Tämän vuoksi hienostuneemmat generaattorit käyttävät useamman [[sana (tietotekniikkaa)|sanan]] (muuttujan) sisäistä tilaa.
Suosittu [[Mersenne Twister]] käyttää 624:n sanan sisäistä tilaa. Se "sekoittaa" koko sisäisen tilansa, sitten tuottaa 624 lukua ajamalla sisäisen tilan sanat yksitellen lyhyen muunnosfunktion läpi. MT on nopea, joskaan ei nopein normaalit statistiset testit läpäisevä pseudosatunnaislukugeneraattori.
== Katso myös ==
|