Generator Fibonacciego

Generator Fibonacciego – jeden z wielu wariantów uogólnionego generatora liniowego liczb losowych.

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

${\displaystyle X_{n}=X_{n-1}+X_{n-2}\,\,\,{\bmod {\,}}m\,(n\geqslant 2)}$

Generator Fibonacciego ma dużo lepsze parametry jakościowe od innych generatorów liniowych, ale wymaga dużo większego nakładu obliczeń przy generowaniu, 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):

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

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

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

Przykład:

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

${\displaystyle x_{n}=x_{n-q}+x_{n-p}\ (\operatorname {mod} \ m)}$

${\displaystyle x_{3}=x_{0}+x_{2}\ (\operatorname {mod} 17)=7+5\ (\operatorname {mod} 17)=12}$

${\displaystyle x_{4}=x_{1}+x_{3}\ (\operatorname {mod} 17)=16+12\ (\operatorname {mod} 17)=11}$

${\displaystyle x_{5}=x_{2}+x_{4}\ (\operatorname {mod} 17)=5+11\ (\operatorname {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:

${\displaystyle X_{n}=X_{n-p_{1}}\diamondsuit X_{n-p_{2}}\diamondsuit X_{n-p_{3}}\diamondsuit \ldots \diamondsuit X_{n-p_{k}}\,\,\,{\bmod {\,}}m\,(n\geqslant p_{k}>\ldots >p_{2}>p_{1}\geqslant 1).}$

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

Na przykład generator Marsagli (Marsa-LFIB4), ${\displaystyle k=4,}$ ${\displaystyle p_{1}=55,}$ ${\displaystyle p_{2}=119,}$ ${\displaystyle p_{3}=179,}$ ${\displaystyle p_{4}=256,}$ ${\displaystyle m=2^{32},}$ ${\displaystyle \diamondsuit =+.}$

Generator Ziffa (Ziff98), ${\displaystyle k=4,}$ ${\displaystyle p_{1}=471,}$ ${\displaystyle p_{2}=1586,}$ ${\displaystyle p_{3}=6988,}$ ${\displaystyle p_{4}=9689.}$ ${\displaystyle \diamondsuit =xor}$

Bibliografia

• G. Marsaglia, A. Zaman, Toward a universal random number generator.