Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Rozdział10Generatoryfizyczneiprogramowe
21
Przykład1.4.Niecha=2,c=1,m=5.DlaXo=2znajdźkolejneliczby
generowaneprzezfunkcję(1.15).
Rozwiązanie:Mamy
X1=(4+1)mod5=0,X2=(0+1)mod5=1,
X3=3mod5=3,X4=7mod5=2,X5=5mod5=0,...(1.16)
Zauważmy,żeprzytakdobranychstałychtengeneratormaokresrówny
zaledwiecztery!
⋄
WprzypadkugeneratoraLehmera,zdefiniowanegowzorem(1.15),je-
gookrespjestrównymin{ź>0:Xi=Xo}iwoczywistysposóbjest
mniejszylubrównym.Cogorsza,wwieluprzypadkachpjestistotnie
mniejszeniżmaksymalnamożliwawartość,czylim.Istniejeszeregtwier-
dzeń,któredlazałożonychparametrówgeneratora(1.15)określajądługość
osiąganegookresu.Podamyterazkilkaprzykładówtakichlematów(patrz
równieżnp.(Jansson1966,Knuth1997,Ripley1987,Wieczorkowski&
Zieliński1997)).
Lemat1.5.Generatormultiplikatywny
Xn+1=(aXn)modm
(1.17)
zestałąm=2LdlaL>4osiągamaksymalnyokresrówny2L12wtedy
itylkowtedy,gdyXojestliczbąnieparzystąoraza=3mod8(czyliajest
podzielneprzez8zresztą3)luba=5mod8.
Przykład1.6.GeneratorRANDU:a=216+3,m=231.
Lemat1.7.Generatormieszany(1.15)osiągapełnyokresmwtedyitylko
wtedy,gdysąspełnionewszystkietrzywarunki:
1.liczbycimniemająwspólnychdzielników,
2.a=1modpdlakażdegoczynnikapierwszegoliczbym(czylikażdej
liczbypierwszejpdzielącejm),
3.a=1mod4,jeżeli4jestdzielnikiemliczbym.
Przykład1.8.Niecha=69069,c=1,m=232.
