2014. december hónap bejegyzései

Véletlenszám-generátorok ciklusideje

Ahogy az előző bejegyzésben írtam, a pszeudovéletlenszám-generátorok ciklushossza alapvető fontosságú alkalmazásuk során, mivel ezt követően a generátor kimenete ismétli korábbi értékeit, így alkalmatlan arra, hogy további statisztikai adatokat gyűjtsünk. A véletlenszám-generátor ciklusidejét meghatározza az, hogy az algoritmus hány bit-en tárolja belső állapotát: egy 32 bit-es véletlenszám-generátor ciklushossza legfeljebb 232 szám lehet.

A következő táblázatban összefoglalom, hogy amennyiben a véletlenszám-generátort pl. zajgenerálásra használjuk fel, a különböző bitszámú és ciklushosszú algoritmusok mennyi idő után fogják magukat ismételni.

Ciklusidő a következő mintavételi frekvenciák esetén:
Bit-ek száma Ciklushossz (szám) 10 kHz 100 kHz 1 MHz 100 MHz
16 65536 6,5 s 0,65 s 0,065 s 0,65 ms
31 2147483648 2,5 nap 6 óra 36 perc 21 s
32 4294967296 5 nap 12 óra 1,2 óra 43 s
48 2,8147E+14 893 év 89 év 8,9 év 4,7 hét
63 9,2234E+18 2,9E+07 év 2,9E+06 év 2,9E+05 év 292 év
64 1,8447E+19 5,9E+07 év 5,9E+06 év 5,9E+05 év 585 év
128 3,4028E+38 1,1E+27 év 1,1E+26 év 1,1E+25 év 1,1E+23 év

A táblázatból jól látható, hogy a rövid bitszámú véletlenszám-generátorok (32 bit és alatta), még egyszerű, jelgenerálási feladatokra sem használhatók igazán, hiszen nagyon könnyen kifuthatunk a rendelkezésre álló ciklusidőből. A 64 bit-es jelgenerátorok ciklusideje már a legtöbb feladatra elegendő. Ami korlát lehet, hogy számos generátor esetén (pl. az LCG-k esetén) az alacsonyabb helyértékű bit-ek ciklusideje már jóval kevesebb, pl. ha 32 bit-et használunk fel egy-egy 64 bit-es számból, akkor a legkisebb helyértékű bit ciklusideje már csak egy 33 bit-es generátorénak felel meg.

Szükség esetén rendelkezésre állnak sokkal nagyobb periódusidejű pszeudovéletlenszám-generátorok is, pl. a Mersene Twister (219937-1 szám), ezek implementálása viszont sokszor túlságosan sok erőforrást igényelhet.

Véletlen számok létrehozása: pzeudovéletlenszám-generátor

A számítógépek determinisztikusak, az általuk végzett műveletek mindig határozott, megjósolható eredményt adnak. Felmerülhet a kérdés, hogy akkor hogyan tudunk vele véletlen folyamatokat modellezni, véletlen számokat létrehozni. Bár számos fizikai folyamat is alkalmas valódi véletlen jelek létrehozására, ezeket pedig digitális számokká alakíthatjuk, e módszer általában túl lassan állítja elő a véletlen számokat ahhoz, hogy szimulációk és mérések számára felhasználhassuk. Éppen ezért az általánosan használt eljárás, hogy algoritmusok segítségével állítunk elő determinisztikus, de véletnennek tűnő számsorozatot. Ezeket az algoritmusokat hívjuk pszeudovéletlenszám-generátornak.

Mivel ezek a generátorok determinisztikusak, meg van az az előnyük, hogy bármikor reprodukálni tudjuk a korábban előállított jelet. Erre a jelgenerátor seed nevű kezdőparaméterét használhatjuk.

Természetesen vannak hátrányai is a pszeudovéletlenszám-generátoroknak. Az egyik, hogy a létrehozott számsornak van egy bizonyos ismétlődési ideje, ennek lejártakor a generátor már pontosan ugyanazt a számsorozatot adja vissza. Ennek oka, hogy a véletlenszám-generátorok meghatározott bitszámon tárolják el belső állapotukat, működésük során pedig előbb utóbb eljutnak egy olyan állapotba, amiben már tartózkodtak valamikor; ezt követően pedig elkezdik ismételni a legenerált számsorozatot. Például egy olyan véletlenszám-generátor ami 16 bit-en tárolja az adatait, legfeljebb 216 létrehozott számsorozatot tud előállítani ismétlés nélkül. Ha segítségével egy olyan zajgenerátort hozunk létre, mely 10 kHz-es mintavételi frekvenciával állít elő fehér zajt, az 6,5 másodperc után már ismétlődni fog, jelentősen korlátozva az alkalmazhatóságát.

A véletlenszám-generátor által létrehozott számsorban, az algoritmustól függően, különböző rövid és hosszú távú kapcsolatok, összefüggések lehetnek. Ezen összefüggések egyes szimulációk során akár hibás eredményre is vezethetnek, amennyiben a véletlenszám-generátor hibája pont torzítja a végeredmény statisztikáját. Ezért fontos, hogy alkalmazás előtt megismerjük véletlenszám-generátorunk tulajdonságait és korlátait.

A véletlenszám-generátorokat számos tesztnek vethetjük alá [1], vizsgálhatjuk a számok eloszlását, az egymás utáni elemek közötti korrelációt, a periódushosszt, a generátor megbízhatóságát jól megfogalmazott és ismert eredményű Monte-Carlo feladatokban. E mellett egy hasznos teszt a spektrálpróba, ahol a legenerált számsorozatból egy térbeli (vagy hipertérbeli ábrát) készítünk, ahol az egymás után legenerált számokból egy-egy pontot ábrázolunk. Ideális esetben ezek a pontok egyenletesen lefednék a teret. Valós esetben a pontok párhuzamos hipersíkokba rendeződnek. Az, hogy hanyadik dimenzióban jelennek meg a hipersíkok, illetve hogy milyen távolság van közöttük, a jelgenerátor típusától és paramétereitől függ. A következő ábrán a Fortran programozási RANDU függvény [2] térbeli eloszlását láthatjuk; már 3 dimenzióban is kialakulnak ezek a síkok. Ez azt jelenti, hogy ha pl. egy szimulációban 3 paramétert szeretnénk egymástól függetlenül változtatni, amennyiben ezzel a függvénnyel hoznánk létre őket, az szimuláció eredménye egyáltalán nem fog megfelelni a valóságnak, hiszen a paraméterek nem lesznek egymástól függetlenek.

A RANDU véletlenszámgenerátor térbeli eredménye

A RANDU véletlenszám-generátor által létrehozott pontok térbeli elhelyezkedése

Olyan pszeudovéletlenszám-generátor nincs, mely minden teszten átmenne, de a legtöbb manapság használt véletlenszám-generátor jól teljesít a tesztek nagy részében, és mindig találhatunk a feladatunkhoz leginkább megfelelő algoritmust.

[1] L’ECUYER, P: Testing random number generators. Proceedings of the 1992 Winter Simulation
Conference, (2002), 305–313. p.

[2] DONALD ERVIN KNUTH: A számítógép-programozás művészete 2. kötet (Szeminumerikus
algoritmusok). Budapest, 1987, Műszaki Könyvkiadó.