Generator Fibonacciego

Z Wikipedii

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

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

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:

gdzie p i q są opóźnieniami generatora.

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

, generator taki oznaczamy .

---

Przykład:

m = 17, p = 3, q = 1, x₀ = 7, x₁ = 16, x₂ = 5

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

x₃ = x₀ + x₂ (mod 17)=7+5 (mod 17)=12

x₄ = x₁ + x₃ (mod 17)=16+12 (mod 17)=11

x₅ = x₂ + x₄ (mod 17)=5+11 (mod 17)=16 itd.

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