algorytm.org

Generator SWBG (Generator Odejmowanie Z Pożyczką)



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 SWBG (Generator Odejmowanie Z Pożyczką)
Ocena użytkowników:***** / 3
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 29 września 2008 00:18

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

Generator Odejmowanie Z Pożyczką (ang. SWBG - Subtract With Borrow Generator) został opracowany w roku 1991 przez G.Marsaglia'e oraz A.Zaman'a. Opisany jest on następującym wzorem:
x_n = (x_{n-j} - x_{n-k} - c_{n-1}) \mod m, 0 < j < k\\ c_n = \begin{cases} 0 & \text{ jeżeli } (x_{n-j} - x_{n-k} - c_{n-1}) \geq 0\\ 1 & \text{ jeżeli } (x_{n-j} - x_{n-k} - c_{n-1}) < 0 \end{cases}
Znaczenie poszczególnych symboli jest następujące:
  • xi i-ta wygenerowana liczba pseudolosowa
  • ci określa czy podczas obliczania i-tej liczby pseudolosowej wynik pośredni (przed dzieleniem modulo) był mniejszy od 0
  • m współczynnik określający zakres generowanych liczb pseudolosowych (od 0 do m-1)

We wzorze tym można zauważyć nieprzypadkowo podobieństwo do Opóźnionego Generatora Fibonnaci'ego (LFG), gdyż generator ten powstał jako jego ulepszenie, polegające na wydłużeniu cyklu ciągu generowanych liczb pseudolosowych. Tak samo jak w tamtym generatorze występują tzw. współczynniki opóźnienia j oraz k, określające, które z poprzednio wygenerowanych liczb użyć do wygenerowania nowej. Nowością jest tutaj natomiast wprowadzenie parametru pożyczki c, który określa, czy wartość przed dzieleniem modulo jest mniejsza od 0, czyli czy nastąpiło przepełnienie wyniku.
Warto też zauważyć iż w przeciwieństwie do Generatora Dodawanie Z Przeniesieniem, kolejność parametrów xn-j oraz xn-k ma znaczenie. Będziemy tutaj rozpatrywać jedynie postać xn-j - xn-k, ale nic nie stoi na przeszkodzie by zaimplementować analogiczny generator z odejmowaniem postaci: xn-k - xn-j.
Generator ten musi pamiętać k ostatnich wygenerowanych liczb. 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 losowymi wartościami z przedziału od 0 do m-1, można wykorzystać w tym celu generator LCG. Początkowa wartość parametru pożyczki c wynosi 0. 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:

if x[(k + i - j) mod k] >= x[i] + c then
  x[i] = x[(k + i - j) mod k] - x[i] - c;
  c = 0;
else
  x[i] = m - ((x[i] + c) - x[(k + i - j) mod k]);
  c = 1;
result = x[i];
i = (i + 1) mod k;


Zauważmy, iż jeżeli operujemy na liczbach 32-bitowych, to maksymalna wartość m dla jakiej możemy użyć powyższej implementacji to 232-2. Wynika to z faktu, iż należy się zabezpieczyć przed przepełnieniem wyniku dodawania x[i] + c. Dla reprezentacji w-bitowej będzie to oczywiście m ≤ 2w-2, gdyż wartości xi są zawsze mniejsze od m, a c jest równe 0 lub 1.
Można też, o ile pozwala na to język programowania, który stosujemy założyć, że m jest liczba dla której dla danej reprezentacji następuje przepełnienie (np. 232). Obliczenie nowego wyrazu przeprowadzamy normalnie, a fakt zaistnienia przepełnienia odczytujemy poprzez wbudowaną w język funkcję.
Pomysłodawcy generatora podają, wiele różnych ograniczeń na zalecane wartości parametrów m, j oraz k, jednym z nich jest następujący warunek: liczba mk - mj - 1 powinna być liczbą pierwszą. W tabeli poniżej zebrano kilka przykładowych wartości tych parametrów. Pierwszy z podanych przykładów znany jest jako generator RANMAR

mjkdługość
cyklu
232-52243~10414 (RANMAR)
2322437~10354
2321924~10228
232621~10200
231848~10445


Przykład:

Załużmy wartości współczynników m=10, j=1, k=3.
Załóżmy, że k-elementowa tablica została zainicjowana następującymi wartościami: x = {2, 7, 4}
Pierwsza wygenerowana wartość:
x[0] = (x[(3+0-1) mod 3] - x[0] - c) mod 10 = (4 - 2 - 0) mod 10 = 2,
wartość przed dzieleniem modulo była większa od 0, a więc c = 0,
x = {2, 7, 4}
Kolejna wygenerowana wartość:
x[1] = (x[(3+1-1) mod 3] - x[1] - c) mod 10 = (2 - 7 - 0) mod 10 = 5,
wartość przed dzieleniem modulo była mniejsza od 0, a więc c = 1,
x = {2, 5, 4}
Kolejna wygenerowana wartość:
x[2] = (x[(3+2-1) mod 3] - x[2] - c) mod 10 = (5 - 4 - 1) mod 10 = 0,
wartość przed dzieleniem modulo była równa 0, a więc c = 0,
x = {2, 5, 0}
Wracamy z powrotem na początek tablicy, kolejna wygenerowana wartość:
x[0] = (x[(3+0-1) mod 3] - x[0] - c) mod 10 = (0 - 2 - 0) mod 10 = 8,
wartość przed dzieleniem modulo była mniejsza od 0, a więc c = 1,
x = {8, 5, 0}
...

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 1
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 1
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 1
 
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: 03 października 2012 14:52
Dodaj komentarz