Univerzita Hradec Králové Fakulta informatiky a managementu
Tester generátorů pseudonáhodných čísel Stochastické modelování Seminární práce č. 1
Autor: Bc. Tomáš Olívka Tématický okruh: 1 Školní rok: 2008–2009 Anotace: Tato práce se zabývá testováním generátorů pseudonáhodných čísel s rovnoměrným rozdělením na intervalu < 0, 1 >. Cílem této práce je vytvořit software, pomocí něhož se dá libovolným kongruenčním generátorem vygenerovat řada pseudonáhodných čísel a následně otestovat vlastnosti takto vzniklé řady.
Univerzita Hradec Králové Fakulta informatiky a managementu
1 Obsah 1 2 3
Obsah.......................................................................................................................... 2 Testování kongruenčních generátorů ......................................................................... 3 Použité metody ........................................................................................................... 3 3.1 Generátory pseudonáhodných čísel .................................................................... 3 3.2 Generování pseudonáhodných čísel ................................................................... 3 3.3 Testy posloupností pseudonáhodných čísel ....................................................... 4 3.3.1 Kolmogorov-Smirnovův test ...................................................................... 4 3.3.2 Test náhodnosti – extremální body ............................................................ 4 3.3.3 Test náhodnosti – test znamének diferencí ................................................ 4 4 Přehled získaných výsledků ....................................................................................... 5 4.1.1 Vygenerovaná čísla .................................................................................... 5 4.1.2 Testy a jejich interpretace .......................................................................... 5 5 Závěr........................................................................................................................... 7 6 Odkazy ....................................................................................................................... 8
Stochastické modelování
Tomáš Olívka
2 Testování kongruenčních generátorů Generátory pseudonáhodných čísel jsou využívány mnoha výpočetními systémy k rozmanitým účelům např. kryptografii nebo simulaci náhodného chování. Pomocí moderní výpočetní techniky se díky tomuto postupu dají vygenerovat v krátkém čase ( řádově desítky milisekund ) dostatečně dlouhé posloupnosti. V praxi je známa celá řada kongruenčních generátorů, na jejichž základě je možné vygenerovat posloupnost pseudonáhodných čísel. Volba generátoru a způsob jeho implementace ovlivňuje rychlost výpočtu i přesnost výsledků. Tato práce se zabývá generováním posloupností pseudonáhodných čísel s rovnoměrným rozdělením na intervalu < 0, 1 > a jejich následným testováním. Testování generátoru náhodných čísel je dnes již velice široká oblast. S rostoucím výkonem počítačů je při simulacích generováno více a více čísel a je proto potřeba vyvíjet lepší a lepší generátory. A aby se o generátoru dalo říct, že je "dobrý", musí procházet testy, jejichž náročnost koresponduje s tím, kolik čísel budeme potřebovat. Dnes to běžně mohou být desítky či stovky miliónů [4]. Cílem této práce je vytvořit software ( dále jen GeneratorTester ), který by dokázal generovat řadu pseudonáhodných čísel z normálního rozdělení pomocí libovolného kongruenčního generátoru určeného vzorcem ( vzorec 1.) a následně tuto řadu otestovat. Software by měl umět výsledky testů interpretovat a vygenerované hodnoty vyjádřit graficky.
3 Použité metody 3.1 Generátory pseudonáhodných čísel Generátory pseudonáhodných čísel jsou založeny na aritmetických procedurách využívajících rekurentní vzorce. Nejužívanější a teoreticky nejpropracovanější jsou kongruenční generátory. Posloupnost čísel je vytvářena podle vztahu
xn+1 = Axn + B(mod M) Vzorec 1.
kde mod M je celočíselný zbytek po dělení M. Vlastnosti této posloupnosti závisí na volbě konstant A, B a M. Posloupnost je sice zcela deterministická, ovšem z hlediska simulovaného problému má vlastnosti náhodné posloupnosti [2].
3.2 Generování pseudonáhodných čísel Pomocí primárního generátoru je generována posloupnost o jejíchž hodnotách se předpokládá, že jsou náhodné, vzájemně nezávislé čísla s rovnoměrným rozdělením. Následně jsou hodnoty vzniklé posloupnosti přetransformovány dělením M do intervalu < 0, 1 >. S takto nově vzniklými hodnotami jsou prováděny testy ( viz. kapitola 3.3 ).
3
Tomáš Olívka 15.11.2008
Stochastické modelování
Tomáš Olívka
3.3 Testy posloupností pseudonáhodných čísel V následujících podkapitolách jsou popsány testy, použité při testování generovaných posloupností. Testují se vždy posloupnosti s transformovanou hodnotu generovaného čísla do intervalu < 0, 1 >
3.3.1 Kolmogorov-Smirnovův test Tento test je způsobem, jak ověřit, zda vzorek empirických hodnot odpovídá jistému pravděpodobnostnímu rozdělení. Je založen na pozorování, že rozdíl mezi sledovanou distribuční funkcí Fn(x), danou empirickými hodnotami, a očekávanou distribuční funkcí F0(x) má být co nejmenší. V našem případě testujeme, zdali empirická rozdělení posloupnosti vygenerovaných čísel se shoduje s očekávaným rozdělením posloupností, která má rovnoměrné rozdělení hodnot v intervalu < 0, 1 >. Jde tedy o test nulové hypotézy H0: rozdělení Fn(x0) je dáno distribuční funkcí F0(x) proti alternativě H1: rozdělení Fn(x0) je dáno jinou funkcí než F0(x).
3.3.2 Test náhodnosti – extremální body Cílem tohoto testu je zjistit nahodilé střídání hodnot v posloupnosti. Test je založen na sledování počtu extremálních bodů v posloupnosti. Nejprve se sečte počet extremálních bodů P v posloupnosti. Pro extremální bod Xn posloupnosti platí, že (Xn < Xn+1 ^ Xn < Xn-1) v (Xn> Xn+1 ^ Xn > Xn-1). Velikost čísla P posloupnosti n prvků může být maximálně n-2. Pro výpočet normované statistky u posloupnosti se využije vztahu:
Normovaná statistika u má normální rozdělení N (0, 1). Testuje se hypotéza H0 zdali je posloupnost stacionárně náhodná proti alternativě, že posloupnost není stacionárně náhodná. H0 se nezamítá, jestliže |u| ≤ u1- α/2
3.3.3 Test náhodnosti – test znamének diferencí Analogicky z předchozího testu je snaha opět zjistit nahodilé střídání hodnot v posloupnosti. Pro tento účel využit celkový počet bodů růstu v posloupnosti, který značíme písmenem C. Pro bod růstu Xn posloupnosti platí, že Xn < Xn-1 Velikost čísla C posloupnosti n prvků může být maximálně n-1. Pro výpočet normované statistky u posloupnosti se využije vztahu:
Rozhodovací pravidlo je stejné jako v testu extremálních bodů ( viz. kapitola 3.3.2 ).
4
Tomáš Olívka 15.11.2008
Stochastické modelování
Tomáš Olívka
4 Přehled získaných výsledků Tato kapitola popisuje výsledky a interpretaci testů, které byly získány z vytvořené aplikace GeneratorTester.
4.1.1 Vygenerovaná čísla GeneratorTester má k dispozici 8 známých kongruenčních generátorů ( obr. 1 ) popsaných v [1], mezi které patří například knihovna IMSL, Unix Rand či knihovna ESSL. Uživatel má také možnost zvolit vlastní generátor určený vzorcem ( vzorec 1.). Počáteční hodnota seed generátoru je ponechána na uživateli. Počet vygenerovaných čísel může být až 1000 000, čímž je zajištěna dostatečně dlouhá řada pro provádění testů.GeneratorTester poskytuje 3 informace o generované hodnotě ( obr. 2 ): 1. pořadí generovaného čísla 2. hodnotu generovaného čísla 3. transformovanou hodnotu generovaného čísla do obr. 1 Generátory intervalu < 0, 1 >
obr. 2 Přehled vygenerovaných čísel na základě zvoleného generátoru
4.1.2 Testy a jejich interpretace Jednotlivé testy jsou prováděny na základě generovaných čísel. Po stisknutí tlačítka generuj, se kromě vygenerování řady čísel provede i následné otestování řady se základním nastavením. Pokud chceme upravit parametry testu, musíme spustit test znovu příslušným tlačítkem ( obr. 3 ). Program na základě zadaných parametrů automaticky vyhodnotí, zdali se nulová hypotéza zamítá.
obr. 3 nastavení parametrů testu + vyhodnocení testu
5
Tomáš Olívka 15.11.2008
Stochastické modelování
Tomáš Olívka
Pro přehlednost jsou k dispozici uvedeny dva grafy: graf rozdělení ( obr. 4 ) , který zpřehledňuje interpretaci Komolgorov-Smirnova testu a graf extrémů ( obr. 5 ) pro testy extrémů a diferencí.
obr. 4 zobrazuje rozdělení hodnot četností do intervalů
obr. 5 Grafická interpretace generované posloupnosti ( extrémy, diference )
6
Tomáš Olívka 15.11.2008
Stochastické modelování
Tomáš Olívka
5 Závěr Podařilo se vytvořit funkční aplikaci, která je schopna vygenerovat dostatečně dlouhé posloupnosti pseudonáhodných čísel ( cca 1000 000 hodnot ). Avšak poskytuje pouze tři typy testů. Proto není možné zcela přesně definovat míru spolehlivosti generátorů. Aplikace tedy slouží jako jednoduchý a účinný nástroj pro generování pseudonáhodných čísel. Při testování je třeba brát v potaz, že se testy týkají pouze určitých vlastností vzniklých řad. Aplikace je navržena tak, aby mohla být v případě potřeby rozšířena o celou řadu dalších testů či grafů. Určitě by bylo vhodné dodělat test Spearmanův pořadový koeficient korelace a test rychlosti generátoru.
7
Tomáš Olívka 15.11.2008
Stochastické modelování
Tomáš Olívka
6 Odkazy [1]
SKALSKÁ, Hana; Stochastické modelování, GAUDEAMUS, 2006, 80-7041-488-X
[2]
GUŠTAR, Milan . Generování náhodně proměnných veličin v metodě Monte Carlo. [s.l.] : [s.n.], 2000. Dostupný z WWW:
. ISBN 80-02-01344-1. s. 1-2.
[3]
ZÁŘECKÝ, Pavel. Generátory pseudonáhodných čísel v prostředí mobilních telefonů. [s.l.], 2008. 32 s. Vedoucí bakalářské práce Mgr. et Mgr. Jan Krhovják. Dostupný z WWW: .
[4]
KAHANEK, P. Generátor náhodných čísel v Matlabu. Konference Matlab B05. 2005, s. 10. Dostupný z WWW: .
7 Přílohy K práci je vyhotoven software GeneratorTester_TO.
8
Tomáš Olívka 15.11.2008
