Dodający Opóźniony Generator Fibonacciego

Algorytm

Podstawowy generator liczb Fibonacciego opiera się na wzorze x_n = x_{n - 1} + x_{n - 1} mod m, gdzie n ≥ 2, a m to dowolna liczba naturalna większa, równa 2. W ten sposób przykładowo dla m = 3 wygenerowany zostanie ciąg: 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2....

Jak można zauważyć ciąg ten posiada pewną wadę jaką jest cykliczność, dlatego definiuje się Opóźniony generator Fibonacciego. Wprowadza on modyfikację we wzorze polegającą na zmianie indeksów poprzednich pozycji na podstawie, których są generowane następne liczby. W ten sposób zwiększa to szansę na uzyskanie bardziej zróżnicowanych danych. Wzór wtedy przybiera postać: x_n = x_{n - p} + x_{n - q} mod m, gdzie można go zastosować dla każdego wyrazu o indeksie większym, równym maksimum zbioru {p, q}.

Przykładowo kiedy zostanie wybrany p = 1, q = 3 i m = 3. Generator wygeneruje kolejno: 0, 1, 1, 1, 2, 0, 1, 0, 0, 1, 1, .. co w przypadku zwiększenia m pozwoliłoby na otrzymanie bardziej zróżnicowanych wartości.

Implementacja

Wstęp

Mechanizmy przedstawionych algorytmów zostały dokładnie wytłumaczone w artykule dotyczącym ciągu Fibonacciego.

Podstawowy generator

Przypuśćmy, że celem jest napisanie programu, który wypisze pierwsze k liczb pseudolosowych dla podanego argumentu m. W tym przypadku można zastosować rozwiązanie iteracyjne, aby proces generowania kolejnych liczb przebiegł jak najszybciej.

1. int generatorFib(int k, int m) {
2.   int a = 0, b = 1, t = 1;
3.   for (int i = 0; i < k; i++) {
4.     t = a;
5.     a = (a + b) % m;
6.     b = t;
7.   }
8.   return a;
9. }

Kluczowa jest tutaj linijka (5.) w której sumę dwóch poprzednich elementów zamienia się na resztę z dzielenia obliczonej sumy podzielonej przez m.

W celu wypisania pierwszych dziesięciu liczb przedstawioną funkcją wystarczy wpisać:

1.   int m = 3;
2.   for(int i = 0; i < 10; i++)
3.     cout << generatorFib(i, m) << endl;

• Kod źródłowy Podstawowy generator