algorytm.org

Generator LFG (Opóźniony Generator Fibonacci'ego)



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Generator LFG (Opóźniony Generator Fibonacci'ego)
Ocena użytkowników:***** / 7
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 29 września 2008 00:10

Generator liczb pseudolosowych (ang. PRNG - Pseudo-Random Number Generator) pozwala na generowanie ciągu liczb, który:
  • jest deterministyczny - zainicjowany tą samą wartością dają zawsze taki sam ciąg pseudolosowych liczb,
  • pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła.

Generatory liczb pseudolosowych znajdują zastosowania w wielu dziedzinach algorytmiki, są to m.in:
  • algorytmy genetyczne - selekcja oraz mutacja
  • algorytmy heurystyczne - symulowane wyżarzanie
  • sztuczna inteligencja - początkowe wartości połączeń pomiędzy neuronami
  • algorytmy probabilistyczne - metody Monte-Carlo

Przypomnijmy sobie na początku jak zdefiniowany jest ciąg Fibonnaci'ego:
x_n = x_{n-1} + x_{n-2}
A więc kolejne wyrazy ciągu powstają poprzez dodanie dwóch poprzednich. Przy czym zakłada się, że dwa początkowe wyrazy wynoszą 1.
Uogólnijmy teraz ten wzór następująco:
x_n = (x_{n-j} @ x_{n-k}) \mod m, 0 < j < k
Uzyskamy w ten sposób Opóźniony Generator Fibonacci'ego (ang. LFG - Lagged Fibonacci Generator). Znaczenie poszczególnych symboli jest następujące:
  • xi i-ta wygenerowana liczba pseudolosowa
  • m współczynnik określający zakres generowanych liczb pseudolosowych (od 0 do m-1)

Przypatrzmy się, co zostało zmienione w stosunku do oryginalnej definicji ciągu. Przede wszystkim zostało wprowadzone dzielenie modulo m, które zapewnia nam generowanie liczb w zakresie <0; m-1>. Uogólniono też operacje wykonywaną na dwóch wyrazach ciągu, @ może być zdefiniowane jako dodawanie, odejmowanie, mnożenie, ... .Zmieniono też definicję wyrazów ciągu poddawanych operacji, nie są to już dwa bezpośrednio poprzednie wyrazy.
W zależności od wybranej operacji wyróżnimy następujące generatory:

  • ALFG - Addytywny Opóźniony Generator Fibonacciego (ang. Additive Lagged Fibonacci Generator) - gdy operacja @ zdefiniowana jest jako dodawanie. Otrzymamy wówczas następującą definicję.
    x_n = (x_{n-j} + x_{n-k}) \mod m, 0 < j < k
    Jeżeli m jest potęgą liczby 2, czyli m = 2M, to maksymalna długość cyklu ciągu generowanego przez ten generator wynosi: (2k - 1)*2M-1

  • MLFG - Multiplikatywny Opóźniony Generator Fibonacciego (ang. Multiplicative Lagged Fibonacci Generator) - gdy operacja @ zdefiniowana jest jako mnożenie. Otrzymamy wówczas następującą definicję.
    x_n = (x_{n-j} * x_{n-k}) \mod m, 0 < j < k
    Jeżeli m jest potęgą liczby 2, czyli m = 2M, to maksymalna długość cyklu ciągu generowanego przez ten generator wynosi: (2k - 1)*2M-3

  • Dwu-punktowy uogólniony rejestr przesuwny ze sprzężeniem zwrotnym - (ang. Two-tap Generalised Feedback Shift Register) - gdy operacja @ zdefiniowana jest jako alternatywa wykluczająca (XOR). Otrzymamy wówczas następującą definicję.
    x_n = (x_{n-j} \xor x_{n-k}) \mod m, 0 < j < k
    Maksymalna długość cyklu ciągu generowanego przez ten generator wynosi: 2k - 1

Generator ten musi pamiętać k ostatnich wygenerowanych słów. W praktyce wykonuje się to poprzez zastosowanie tablicy o k elementach. Tablicę taką traktuje się jak rejestr cykliczny, tzn. iterując po kolejnych elementach dochodząc do końca tablicy przechodzimy z powrotem na jej początek. Łączymy niejako koniec i początek tej tablicy tworząc cykl. Zatem odwołanie do elementu n-j, dla k-elementowej tablicy będzie pod indeksem (n-j+k) mod k. Kolejne wywołania funkcji obliczają wartości w tablicy od indeksu 0 do k-1 po czym znów zaczynają obliczać wartości dla indeksu 0. Początkowo tablica ta musi zostać zainicjowana jakimiś losowymi wartościami z przedziału od 0 do m-1, można wykorzystać w tym celu generator LCG. Cały algorytm można przedstawić następująco, niech x będzie wspomnianą tablicą, natomiast i będzie wewnętrznym wskaźnikiem określającym aktualne przesunięcie w tablicy:

x[i] = (x[(k + i - j) mod k] @ x[i]) mod m;
result = x[i];
i = (i + 1) mod k;


Pozostało nam zatem określenie wartości j oraz k. By generator miał maksymalny możliwy cykl wartości te należy dobrać tak by wielomian xk + xj + 1 był wielomianem prostym. Poniżej w tabeli zestawiono popularne wartości tych współczynników:

jk
517
631
710
2455
3163
6571
97127
128159
168521
273607
334607
353521
4181279

Przykład:

Załużmy, że operacja @ jest zdefiniowana jako dodawanie, czyli mamy do czynienie z generatorem ALFG.
Wartości współczynników m=128, j=7, k=10.
Załóżmy, że k-elementowa tablica została zainicjowana następującymi wartościami: x = {29, 8, 19, 83, 72, 9, 15, 62, 11, 25}

Pierwsza wygenerowana wartość:
x[0] = (x[(10+0-7) mod 10] + x[0]) mod 128 = (83+29) mod 128 = 112,
x = {112, 8, 19, 83, 72, 9, 15, 62, 11, 25}

Kolejna wygenerowana wartość:
x[1] = (x[(10+1-7) mod 10] + x[1]) mod 128 = (72+8) mod 128 = 80,
x = {112, 80, 19, 83, 72, 9, 15, 62, 11, 25}

Kolejna wygenerowana wartość:
x[2] = (x[(10+2-7) mod 10] + x[2]) mod 128 = (9+19) mod 128 = 28,
x = {112, 80, 28, 83, 72, 9, 15, 62, 11, 25}

Kolejna wygenerowana wartość:
x[3] = (x[(10+3-7) mod 10] + x[3]) mod 128 = (15+83) mod 128 = 98,
x = {112, 80, 28, 98, 72, 9, 15, 62, 11, 25}

Kolejna wygenerowana wartość:
x[4] = (x[(10+4-7) mod 10] + x[4]) mod 128 = (62+72) mod 128 = 6,
x = {112, 80, 28, 98, 6, 9, 15, 62, 11, 25}

...

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 3
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 1
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 2
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 stycznia 2013 15:53
Dodaj komentarz