Näennäissatunnaislukugeneraattori
Wikipedia
Näennäissatunnaislukugeneraattori (valesatunnaislukugeneraattori, pseudosatunnaislukugeneraattori) on matemaattinen algoritmi, joka annetun siemenen perusteella pyrkii 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 esim. 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.
[muokkaa] 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. Jokaisella näennäissatunnaislukugeneraattorilla on siis toistuva jakso.
Lineaarisessa näennäsissatunnaisulukugeneraattorissa luku kerrotaan sopivalla vakiolla ja tuloksesta otetaan jakojäännös.
xn+1 = c * xn mod m
Jotta jaksosta saadaan mahdollisimman pitkä, luvut c ja m on valittava erittäin hyvin. Käytännössä parhaat tulokset on mahdollista saavuttaa alkuluvuilla.
Esimerkiksi arvoilla c=23 ja n=101 ja siemenen ollessa 1:
xn+1 = 23 * xn mod 101
saadaan satunnaislukujen jonoksi 1,23,24,47,71,17,..
