algorytm.org

Generator AWCG (Generator Dodawanie Z Przeniesieniem)

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 AWCG (Generator Dodawanie Z Przeniesieniem)
Ocena użytkowników:***** / 2
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 29 września 2008 00:14

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 Dodawanie Z Przeniesieniem (ang. AWCG - Add With Carry 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}) < m\\ 1 & \text{ jeżeli } (x_{n-j} + x_{n-k} + c_{n-1}) \geq m \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 nastąpiło przepełnienie
  • 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 przeniesienia c, który określa, czy suma elementów jest większa od parametru m, czyli czy nastąpiło przepełnienie wyniku.
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 jakimiś losowymi wartościami z przedziału od 0 do m-1, można wykorzystać w tym celu generator LCG. Początkowa wartość parametru przeniesienia 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:

result = (x[(k + i - j) mod k] + x[i] + c) mod m;
if (x[(k + i - j) mod k] + x[i] + c) < m then
  c = 0;
else
  c = 1;
x[i] = result;
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 231-1. Wynika to z faktu, iż należy się zabezpieczyć przed przepełnieniem wyniku dodawania. Dla reprezentacji w-bitowej będzie to oczywiście m ≤ 2w-1-1, gdyż wartości xi są zawsze mniejsze od m, a c jest równe 0 lub 1.
Jeżeli pozwala na to język programowania, którego używamy, możemy założyć iż m jest liczbą dla której następuje przepełnienie w wewnętrznej reprezentacji (np. 232), a fakt zaistnienia przepełnienia odczytywać 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ą.

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 = 6,
wartość przed dzieleniem modulo była mniejsza od 10, a więc c = 0,
x = {6, 7, 4}
Kolejna wygenerowana wartość:
x[1] = (x[(3+1-1) mod 3] + x[1] + c) mod 10 = (6 + 7 + 0) mod 10 = 3,
wartość przed dzieleniem modulo była większa od 10, a więc c = 1,
x = {6, 3, 4}
Kolejna wygenerowana wartość:
x[2] = (x[(3+2-1) mod 3] + x[2] + c) mod 10 = (3 + 4 + 1) mod 10 = 8,
wartość przed dzieleniem modulo była mniejsza od 10, a więc c = 0,
x = {6, 3, 8}
Wracamy z powrotem na początek tablicy, kolejna wygenerowana wartość:
x[0] = (x[(3+0-1) mod 3] + x[0] + c) mod 10 = (8 + 6 + 0) mod 10 = 4,
wartość przed dzieleniem modulo była mniejsza od 10, a więc c = 1,
x = {4, 3, 8}
...

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:57
Dodaj komentarz