Wpisany przez Tomasz Lubiński,
29 września 2008 00:02
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:
Generator Park-Miller, jest odmianą Multiplikatywnego Liniowego Generatora Kongruencyjnego określonego następującym wzorem:
Wartość x0 inicjuje generator i zwana jest ziarnem (ang. seed). Generator zawsze generuje takie same wartości liczb pseudolosowych dla określonej wartości ziarna. W przeciwieństwie do ogólnego generatora współczynniki a oraz m muszą spełniać określone warunki.
Wszystkie współczynniki w tym generatorze muszą być dobrane starannie by w wygenerowanym ciągu nie wystąpiło 0. W takim przypadku po wystąpieniu tej wartości generator staje się bezużyteczny i zaczyna generować ciąg zer. Oto kilka przykładów współczynników dla generatora Park-Miller:
- 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 Park-Miller, jest odmianą Multiplikatywnego Liniowego Generatora Kongruencyjnego określonego następującym wzorem:
x_i = (a*x_{i-1}) \mod m
Znaczenie poszczególnych symboli jest następujące:- xi i-ta wygenerowana liczba pseudolosowa
- a współczynnik generujący kolejną liczbę pseudolosową
- m współczynnik określający zakres generowanych liczb pseudolosowych (od 0 do m-1)
Wartość x0 inicjuje generator i zwana jest ziarnem (ang. seed). Generator zawsze generuje takie same wartości liczb pseudolosowych dla określonej wartości ziarna. W przeciwieństwie do ogólnego generatora współczynniki a oraz m muszą spełniać określone warunki.
- m musi być liczbą pierwszą bądź jej wielokrotnością
- a musi być pierwiastkiem pierwotnym modulo m, czyli dla dowolnego b takiego, że NWD(b, m) = 1 istnieje liczba całkowita k taka, że ak mod m = b
- x0 musi być względnie pierwsze z n,czyli NWD(x0, n) = 1
Wszystkie współczynniki w tym generatorze muszą być dobrane starannie by w wygenerowanym ciągu nie wystąpiło 0. W takim przypadku po wystąpieniu tej wartości generator staje się bezużyteczny i zaczyna generować ciąg zer. Oto kilka przykładów współczynników dla generatora Park-Miller:
Nazwa | m | a |
MINSTD | 231-1 | 16807 |
CRAY/RANF | 248 | 44485709377909 |
- | 216+1 | 75 |
- | 232-5 | 279490273 |
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C# | MS Visual Studio .net | .cs | .cs | ***** / 1 |
Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 1 | |
Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 1 | |
Tomasz Lubiński | Java | .java | .java | ***** / 1 |
Poprawiony: 03 października 2012 14:57