algorytm.org

Generator Park-Miller

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 Park-Miller
Ocena użytkowników:***** / 4
SłabyŚwietny 
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:
  • 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:

Nazwama
MINSTD231-116807
CRAY/RANF24844485709377909
-216+175
-232-5279490273

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