Näennäissatunnaislukugeneraattori

Näennäissatunnaislukugeneraattori (valesatunnaislukugeneraattori, pseudosatunnaislukugeneraattori) on matemaattinen algoritmi, joka pyrkii annetun siemenen perusteella luomaan mahdollisimman satunnaisen luvun. Luonnollisesti pelkillä matemaattisilla operaatioilla ei voida luoda täysin satunnaista lukua, minkä vuoksi puhutaankin näennäissatunnaisluvuista.

Tyypillinen näennäissatunnaislukugeneraattori tuottaa tasajakautuneella todennäköisyydellä lukuja välillä 0...1, jonka jälkeen arvottu luku voidaan muokata jonkun muun jakauman mukaiseksi.

Satunnaislukugeneraattorin tasoa arvioidaan sen perusteella, kuinka sen tuottama satunnaislukujono käyttäytyy. Hyvä generaattori pystyy tuottamaan suunnattoman määrän toisistaan riippumattomia satunnaislukuja joiden jakauma noudattaa satunnaisjakaumaa. Huono generaattori tuottaa vain esimerkiksi tuhannen luvun jonon, jonka jälkeen lukujono alkaa toistaa itseään. Tällöin myös merkkijonon jakauma on epätasainen, ja satunnaisuuden näennäinen matkiminen ei toteudu.

Käytännön satunnaislukugeneraattorit

Tyypillinen näennäissatunnaislukugeneraattori laskee seuraavan arvon edellisestä satunnaisluvusta jollain sopivalla funktiolla.

xn+1 = f(xn)

Ensimmäinen luku on valittava, ja sitä sanotaan siemeneksi. Mikäli satunnaisluvuksi tulee sama kuin siemenestä, koko kierros alkaa identtisenä alusta. Siemenluku haetaan yleisimmin tietokoneen kellosta.

Tunnettu näennäissatunnaislukugeneraattori on 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 log2(c) -bittisillä kokonaisluvuilla, myös AND-operaatio voidaan ohittaa koska c:n ylittävä osa luvusta ”leikkaantuu” pois kokonaislukuylivuodon avulla.

Numerical recipes in C[1] mainitsee LCG:n jossa a=1664525, b=1013904223 ja c=232. Tämän generaattorin jakso on 232.

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 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

Lähteet
  1. Press, William H.: Numerical Recipes in C: The Art of Scientific Computing. , 1992. ISBN 0-521-43108-5. Teoksen verkkoversio.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.