Generator Fibonacciego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Generator Fibonacciego jest jednym z wielu wariantów uogólnionego generatora liniowego liczb losowych.

Generator korzysta z ciągu Fibonacciego, stąd wzór:

X_{n}=X_{n-1}+X_{n-2} \,\,\, mod \, m \, (n\geqslant2)

Generator Fibonacciego ma dużo lepsze parametry jakościowe od innych generatorów liniowych, ale wymaga dużo większego nakładu obliczeń przy generacji, co wiąże się z czasem. Wadą tego generatora są duże korelacje między wyrazami ciągu. Ciągi te spełniają warunek rozkładu, ale nie spełniają warunku niezależności. Wady tej można się pozbyć poprzez uogólnienie wzoru do postaci (tzw. lagged Fibonacci generator):

X_{n}=X_{n-p}+X_{n-q} \,\,\, mod \, m \, (n\geqslant p, \,p>q \geqslant 1) gdzie p i q są opóźnieniami generatora.

Generator taki można jeszcze bardziej uogólnić zastępując działanie dodawania innym operatorem \diamondsuit, np. operatorem odejmowania, mnożenia, XOR itd.

X_{n}=X_{n-p} \diamondsuit X_{n-q} \,\,\, mod \, m \, (n\geqslant p, \,p>q \geqslant 1), generator taki oznaczamy  F(p,q,\diamondsuit) .

Przykład:

m=17, p=3, q=1, x_{0}=7, x_{1}=16, x_{2}=5

x_{n}=x_{n-p}+x_{n-q} (mod m)

x_{3}=x_{0}+x_{2} (mod 17)=7+5 (mod 17)=12

x_{4}=x_{1}+x_{3} (mod 17)=16+12 (mod 17)=11

x_{5}=x_{2}+x_{4} (mod 17)=5+11 (mod 17)=16 itd.

7, 16, 5, 12, 11, 16, 11, 5, 4, 15, 3, 7, ...

Kolejnym uogólnieniem jest użycie większej ilości poprzednich punktów:

X_{n}=X_{n-p_1} \diamondsuit X_{n-p_2} \diamondsuit X_{n-p_3} \diamondsuit \cdots \diamondsuit X_{n-p_k} \,\,\, mod \, m \, (n\geqslant p_k > \dots > p_2 > p_1 \geqslant 1).

Kilka znanych generatorów tego typu przedstawiono poniżej:

Na przykład generator Marsagli (Marsa-LFIB4), k=4, p_1=55, p_2=119, p_3=179, p_4=256, m=2^{32}, \diamondsuit = +.

Generator Ziffa (Ziff98), k=4, p_1=471, p_2=1586, p_3=6988, p_4=9689. \diamondsuit = xor