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:

$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):

$X_{n}=X_{n-p}+X_{n-q}\,\,\,{\bmod {\,}}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-q}\diamondsuit X_{n-p}\,\,\,{\bmod {\,}}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-q}+x_{n-p}\ (\operatorname {mod} \ m)$

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

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

$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:

$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).$