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.

Hozzászóllások