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:
Generatory liczb pseudolosowych znajdują zastosowania w wielu dziedzinach algorytmiki, są to m.in:
Przypomnijmy sobie na początku jak zdefiniowany jest ciąg Fibonnaci'ego:
Uogólnijmy teraz ten wzór następująco:
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:
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:
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}
...
- 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 < kJeż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 < kJeż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 < kMaksymalna długość cyklu ciągu generowanego przez ten generator wynosi: 2k - 1
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:
j | k |
5 | 17 |
6 | 31 |
7 | 10 |
24 | 55 |
31 | 63 |
65 | 71 |
97 | 127 |
128 | 159 |
168 | 521 |
273 | 607 |
334 | 607 |
353 | 521 |
418 | 1279 |
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
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C# | MS Visual Studio .net | .cs | .cs | ***** / 3 |
Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 1 | |
Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 1 | |
Tomasz Lubiński | Java | .java | .java | ***** / 2 |
Poprawiony: 30 stycznia 2013 15:53