Generator LFG

Opóźniony generator Fibonacciego, zwany generatorem LFG ma nazwę wynikającą z podobieństwa wzoru, który jest wykorzystywany w algorytmie LFG do definicji ciągu Fibonacciego.

Ciąg Fibonacciego:

LFG:

Gdzie:

• xIndeks dolny ii – kolejna wygenerowana liczba,

• m – zakres generowanych liczb od 0 do m - 1,

• @ – dowolne działanie np. dodawanie, odejmowanie.

Algorytm wykorzystuje do działania tablicę liczb o długości k. Wartości j i k są tak ustalone, by wynikiem generatora był najdłuższy możliwy cykl wartości.

Obliczenie kolejnej wartości xIndeks dolny ii polega na dodaniu do siebie wartości z tablicy x[] o indeksach j - 1 i k - 1. Następnie indeks elementu tablicy przesuwany jest w lewo o jedno miejsce, a na ostatniej pozycji umieszczana jest wyliczona wartość pseudolosowa.

Dane:

• j i k – współczynniki,

• m – zakres generowanych liczb od 0 do m - 1,

• x[k] – k - elementowa tablica,

• n – ilość liczb do wygenerowania.

ile = 0
dopóki ile < n wykonuj:
	dla i = 0, 1, 2, ..., k - 1 wykonuj:
    	jeżeli x[0] == 0 wykonaj:
        	wynik = (x[j - 1] @ x[k - 1]) mod m
        jeżeli i < k - 1 wykonaj: 
        	x[i] = x[i + 1]
        w przeciwnym wypadku wykonaj:
        	x[i] = wynik
            wypisz wynik

j = 3
k = 7
x[k] = {4, 2, 9, 1, 10, 7, 3}