Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
22
1040Wybranetypygeneratorówprogramowych
1.4.2.
GeneratoryFibonacciego
NazwiskoFibonacciegozwiązanejestzesłynnymrekurencyjnymciągiem
Xn=Xn11+Xn12dlan>2,
(1.18)
gdzieXo=X1=1.Podobnydoniegociąg(patrz(Taussky&Todd1956))
Xn=(Xn11+Xn12)
modmdlan>2
(1.19)
generujeliczby,któremożnawpewnymprzybliżeniuuznaćzalosowe.Testy
statystycznenieodrzucająhipotezy,iżciąg(Xi)il1wygenerowany(1.19)
pochodzizrozkładujednostajnego,aleodrzucająhipotezę,iżciągtenjest
ciągiemzmiennychniezależnych.Wzwiązkuztymuogólnionowzór(1.19)
dopostaci
Xn=(Xn1s+Xn1r)
modmdlan>r,r>s>1.
(1.20)
Jesttotzw.ALFG(AdditiveLaggedFibonacciGenerator).Wprzeszło-
ścitakiegeneratorybyłyjednakrzadkostosowane,zewzględunaswoją
mniejsząszybkośćodgeneratorówmultiplikatywnychikoniecznośćprze-
chowywaniawiększejliczbywcześniejwygenerowanychwartości.Obecnie
jednak,dziękiszybkimkomputeromitańszejpamięci,sąznacznieczęściej
spotykane.Cowięcej,mogąonemiećwiększyokresniżgeneratorymultipli-
katywne.Dlam=2LmaksymalnyokresALFGwynosi(2r−1)2L11.Jak
łatwozauważyć,ALFGjestszczególnymprzypadkiemgeneratoraliniowe-
go(1.14).
Generatorypostaci(1.20)możnauogólnićdowzoru
Xn=(Xn1s⋄Xn1r)
modm,
(1.21)
gdzie⋄jestpewnąoperacją(np.dodawaniem,odejmowaniem,mnożeniem).
WprzypadkumnożeniamówimyoMLFG(MultiplicativeLaggedFibo-
nacciGenerator),ajegomaksymalnyokreswynosi(2r−1)2L13.
DowodywspomnianychtwierdzeńdotyczącychokresuALFGiMLFG
znaleźćmożnanp.w(Marsaglia1985)i(Marsaglia&Tsay1985).
Przykłademuogólnieniamożeteżbyćzastosowanieoperacjibitowejxor,
codajealgorytmzwiązanyzgeneratoramiopartyminarejestrachprzesuw-
nych(np.Two-tapGeneralisedFeedbackShiftRegister).
