Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
20
1040Wybranetypygeneratorówprogramowych
•uznaniowośćwyborutestówstatystycznych–możesięniestetyzda-
rzyć,żewszystkiewcześniejwykorzystywanetestynieodrzucałyhi-
potezy,iżdanyalgorytmgenerujeliczby(pseudo)losowe,alenowy,
dodatkowytestmożetakąhipotezęodrzucić,
•problemwyboruciągu–możesięzdarzyć,żealgorytmgenerujelicz-
byuznaneprzeznasza(pseudo)losowedlawszystkichprzebadanych
najpierwciągów,alepewiennowy,dłuższyciąglubnoweparame-
tryinicjalizującealgorytmdoprowadządoodrzuceniahipotezyotym,
żedanyalgorytmgenerujeliczby(pseudo)losowe.
Wzwiązkuztymniezbędnyjestwybórodpowiednioszerokiegozbio-
rutestówstatystycznych(jaknp.testywkolekcjinDiehard”,nCrypt-XS”,
nDieHarder”,patrznp.(Marsaglia1995))orazsprawdzenieszerokiegospek-
trumciągówiparametrówstartowychgeneratora.Innepodejściewymaga
ścisłegomatematycznegodowodu,żealgorytmgenerujeodpowiednieliczby
losowe.Choćjestonościślejszeinpewniejsze”,wprzypadkuwielutypów
PRNGodpowiedniedowodyniesąznane.
1.4.
Wybranetypygeneratorówprogramowych
1.4.1.
GeneratorLehmera
Generatoremliniowym(LCG–LinearCongruentialGenerator)nazy-
wamygeneratoropisanyfunkcją
Xn+1=(a1Xn+a2Xn11+...+akXn1k+1+c)
modm
(1.14)
gdziea1,a2,...,ak,c,msąliczbamicałkowitymi,zwanymiparametramige-
neratora.Jeślistałac=0,tomówimyogeneratorzemultiplikatywnym,
adlac/=0mówimyogeneratorzemieszanym.
Jakłatwozauważyć,dlageneratorapostaci(1.14)zmiennymiinicjalizu-
jącymijegodziałaniesąXo,X1,...,Xk11,czylikzmiennychwporównaniu
dojednejzmiennejwymaganejprzyalgorytmievonNeumanna.
Najprostszygeneratorliniowymapostać
Xn+1=(aXn+c)modm.
(1.15)
OkreślanyjestonrównieżjakogeneratorLehmera(patrz(Lehmer1951)).
Generatorytakiesączęstoużywanewstandardowychbibliotekachikompi-
latorach.
