Strona główna » Algorytmy » Artykuły » Opóźniony Generator Fibonacciego
 

Opóźniony Generator Fibonacciego

https://mattomatti.com/a0219

Wstęp

Opóźniony Generator Fibonacciego jest używany do generowania ciągu liczb pseudolosowych na podstawie dwóch poprzednich wyrazów, ale niekoniecznie muszą to byś dwa ostatnie wyrazy. Kolejny wyraz można wyliczyć dowolną operacją arytmetyczną lub binarną. W tym artykule zostanie wyjaśnione jak napisać uniwersalny kod. Prostszą wersję tego algorytmu można znaleźć tutaj.

Definicja

Przed przystąpieniem do generowania liczb pseudolosowych należy podać k + 1 początkowych wyrazów, zakres m, aby ograniczyć liczby pseudolosowe do pewnego zakresu (nie jest to konieczne, gdy chcemy wykorzystać pełną pojemność zmiennej) oraz operację, która ma zostać wykonana na wybranych wartościach. Matematycznie można to zapisać jako:

an = an-1 # an-k, gdzie # to wybrana operacja

Choć zasada generowania nie jest trudna to nie jest łatwo wybrać odpowiednie wartości początkowe, aby faktycznie za każdym razem otrzymać nową liczbę losową. Należy jednak pamiętać, że im większa losowość początkowych wyrazów i im więcej ich jest to tym dłużej będą otrzymywane liczby losowe.

Przykład

Przypuśćmy, że liczymy przy pomocy operacji dodawania ciąg dla początkowych wyrazów 1, 2, 3 i k = 2. Zakres ograniczamy przez mod 10. Kolejne wyrazy wtedy to: 1, 2, 3, 4, 6, 9, 3, 9, 8, 1, 0, 8, 9, 9, 7, 6, .. Jak można zauważyć pomimo tego, że początkowe wyrazy to pierwsze liczby naturalne to algorytmowi udało się wylosować "losowy" ciąg.

Wybór operacji

Dodawanie / Odejmowanie

Wspomniane operacje arytmetyczne nie prowadzą do wygaśnięcia ciągu, ale ich wadą jest to, że wyrazy po pewnym czasie zaczynają się powtarzać. Jednak dobrze dobrane wartości początkowe ciągu mogą pozwolić wygenerować bardzo dużo losowych liczb.

Operacja XOR

Operacja XOR generuje ciągi, które początkowo są losowe, ale po pewnym czasie jego ostatnie kilka wyrazów zaczynają się powtarzać. Problem ten można rozwiązać np. poprzez zmianę losowego bitu.

Operacja AND

Operacja AND jest bardzo wrażliwa i po wylosowaniu kilku liczb ciąg jest stały i najczęściej ma wartość 0. Możliwe są inne wartości jeśli we wszystkich początkowych wyrazach pewien bit był ustawiony na wartość 1.

Operacja OR

Analogicznie do operacji AND po pewnym czasie ciąg robi się stały. W tym jednak przypadku powtarzająca się wartość będzie wykonaniem operacji OR na wszystkich wyrazów początków.

Implementacja

Funkcja do generowania liczb będzie przyjmować kolejno: op - znak operacji do wykoanania, m - wartość określająca górny zakres losowanych liczb, zakres wyniesie [0, m], dane - lista wyrazów początkowych, k - cofnięcie wyboru poprzedniego wyrazu oraz n - ile wyrazów ma być na liście (licząc z podanymi wartościami początkowymi).

  1. static List<uint> Generator(char op, uint m, List<uint> dane, int k, int n) {
  2.   for (int i = dane.Count - 1; i + 1 < n; i++) {
  3.     uint a = dane[i];
  4.     uint b = dane[i - k];
  5.     dane.Add(WykonajOperacje(a, b, op) % m);
  6.   }
  7.   return dane;
  8. }

Algorytm składa się z pętli, która dopisze n minus aktualna długość tablicy wyrazów. Generowanie polega na pobraniu dwóch odpowiednich wyrazów, a następnie wykonaniu wybranej operacji arytmetycznej. W tym celu została napisana specjalna funkcja WykonajOperacje(), która wykona operację op na wyrazach a i b.

  1. static uint WykonajOperacje(uint a, uint b, char op) {
  2.   switch (op) {
  3.     case '&': return a & b;
  4.     case '|': return a | b;
  5.     case '^': return a ^ b;
  6.     case '*': return a * b;
  7.     case '+': return a + b;
  8.     case '-': return a - b;
  9.   }
  10.   return 0;
  11. }

Testowanie funkcji

W celu przetestowania napisanych funkcji można skorzystać z poniższego kodu:

  1. static void Main(string[] args) {
  2.   Console.Write("Podaj operacje\n op = ");
  3.   char op = Console.ReadLine()[0];
  4.   Console.Write("Podaj zakres (od 0 do m)?\n m = ");
  5.   uint m = Convert.ToUInt32(Console.ReadLine());
  6.   Console.Write("Ile wyrazów wypisać?\n n = ");
  7.   int n = Convert.ToInt32(Console.ReadLine());
  8.   Console.Write("Który wyraz wstecz?\n k = ");
  9.   int k = Convert.ToInt32(Console.ReadLine());
  10.   List<uint> dane = new List<uint>();
  11.   Console.WriteLine("Podaj {0} pierwszych wyrazów", k + 1);
  12.   string[] wyrazy = Console.ReadLine().Split(' ');
  13.   for (uint i = 0; i < k + 1; i++) {
  14.     dane.Add(Convert.ToUInt32(wyrazy[i]));
  15.   }
  16.   List<uint> wynik = Generator(op, m, dane, k, n);
  17.   foreach(uint x in wynik) {
  18.     Console.Write("{0} ", x);
  19.   }
  20.   Console.ReadKey();
  21. }