algorytm.org

Generator LCG (Liniowy Generator Kongruentny)

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 LCG (Liniowy Generator Kongruentny)
Ocena użytkowników:***** / 18
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 13 września 2008 14:17

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

Najbardziej znanym sposobem generowania liczb pseudolosowych jest metoda opracowana przez Lehmer'a w 1951 zwana liniowym generatorem kongruentnym (ang. LCG - Linear Congruential Generator). Polega ona na obliczaniu kolejnych liczb pseudolosowych: x1, x2, ... xn o zakresie wartości 0 .. m-1 na podstawie poniższego wzoru:
x_i = (a * x_{i-1} + 1) \mod m
gdzie: x1 jest początkową wartością, którą inicjuje się generator - tzw. ziarnem (ang. seed).

Warto zauważyć, że cechą tego generatora jest fakt, iż jeżeli kolejna wygenerowana liczba powtarza się w ciągu liczb już wygenerowanych to wpadamy w cykl: x1, x2, x3, ..., x1, x2, x3, ....
Jeżeli zainicjujemy kolejne generowanie liczbą x2, to otrzymamy oczywiście ciąg: x2, x3, ..., x1, x2, x3, .... W praktyce, jeżeli chcemy uzyskać nieznany ciąg to inicjujemy taki generator wartością, która nie będzie znana w momencie wykonywania programu - np. wartością zegara systemowego. Czasem jednak właściwość generowania znanego ciągu na podstawie wartości ziarna jest jak najbardziej pożądana - na przykład podczas szyfrowania metodą XOR.

Na temat tego prostego wzoru powstało bardzo dużo opracowań i analiz matematycznych, które mówią nam jakie najlepiej dobrać współczynniki m oraz b w celu uzyskania dobrego generatora liczb pseudolosowych. Dobrego, czyli takiego, w którym cykl będzie jak najdłuższy. Łatwo zauważyć, że maksymalna długość cyklu takiego generatora wynosi m.
  • m powinno być duże, często wybiera się tutaj potęgi 10 albo 2,
  • a nie powinno być zbyt duże, ale też nie za małe - dobrym wyborem jest tutaj liczba o jeden rząd mniejsza (o jedną cyfrę krótsza) od m,
  • dobrą wartością a jest liczba postaci t21, gdzie t jest liczbą parzystą.
D.E.Knuth pokazał, iż niektóre wartości mogą prowadzić do wygenerowania bardzo, krótkich cykli co oczywiście jest wysoce niepożądane. Na przykład dla b=19, m=381 oraz x1=0 otrzymamy sekwencję: 0, 1, 20, 0, 1, 20, ...

Generator opracowany przez Lehmer'a możemy uogólnić następująco:
Generator mieszany
x_i = (a * x_{i-1} + c) \mod m
Generator multiplikatywny
x_i = (a * x_{i-1}) \mod m


Generatory używane w praktyce posiadają następujące wartości współczynników:
Nazwamac
Numerical Recipes23216645251013904223
Borland C/C++232226954771
GNU Compiler Collection232690695
ANSI C232110351524512345
Borland Delphi, Virtual Pascal2321347758131
Microsoft Visual/Quick C/C++2322140132531011
ANSIC231110351524512345
MINSTD231-1168070
RANDU231655390
SIMSCRIPT231-16303600160
BCSLIB235305175781257261067085
BCPL2322147001325715136305
URN122314528070530
APPLE23512207031250
Super-Duper232690690
FISH231-19507063760
SIMULA235305175781250
NAG2593028751065922530
DRAND 482482521490391711
CRAY248444857093779090
MAPLE1012-114276196690810
DERIVE23231415926531
CRAND2326636089410


Algorytm obliczania (a * b) mod m bez przepełnienia

Zwróćmy uwagę, iż bardzo prawdopodobne jest wykroczenie poza zakres reprezentacji liczb w programie w miejscu mnożenia a * xi-1. Gdy zachodzi taka sytuacja, następuje przerwanie programu z powodu wystąpienia wyjątku przepełnienia. Bądź, jeżeli język, który zastosowaliśmy nie sprawdza takiej sytuacji, dochodzimy do sytuacji, w której cykl naszego generatora ulega skróceniu, co oczywiście jest cechą niepożądaną. Poniżej przedstawiono algorytm, który pozwala obliczać wartość (a * x) mod m dla wartości m < zakres reprezentacji liczb / 2. Czyli jeżeli w naszym programie użyjemy 64-bitową reprezentację liczb, wówczas możemy obliczyć wszystkie takie operacje dla m < 263, co oczywiście pozwala nam na użycie dowolnego generatora przedstawionego w tabelce powyżej.

Rozłóżmy na początek liczbę a na jej reprezentację binarną:
a = a_0*2^0 + a_1*2^1 + ... + a_n*2^n
gdzie n oznacza liczbę bitów reprezentującą daną liczbę.
Zatem mnożenie a * x możemy teraz przedstawić jako:
(a_0*2^0 + a_1*2^1 + ... + a_n*2^n) * x
Co daje nam:
a_0*2^0*x + a_1*2^1*x + ... + a_n*2^n*x = a_0*(2^0*x) + a_1*(2^1*x) + ... + a_n*(2^n*x)
Zauważmy, że współczynniki ai są równe 0 bądź 1. Zatem przedstawiony powyżej wzór sprowadza się do dodania odpowiednich iloczynów (2i*x). Każdy taki iloczyn występujący we wzorze jest dwa razy większy od poprzedniego więc cały algorytm mnożenia możemy przedstawić następująco:

b = 1;
n = 1;
result = 0;
while (n <= 64) /* Dla wszystkich bitów w reprezentacji */
{
  if(a & b != 0) /* dla bitów różnych od 0 */
  {
     result = (result + x) % m;
  }
  x = (x + x) % m /* Obliczanie kolejnego współczynnika (2i*x) */
  b = 2 * b;
  n = n + 1;
}
return result;


Generowanie liczb pseudolosowych z zakresu <a, b>

Jeżeli chcemy wygenerować ciąg liczb pseudolosowych z zadanego zakresu, nie powinniśmy modyfikować współczynnika m w przytoczonych przykładach. Parametry przedstawione w nich są tak dobrane by osiągnąć jak najdłuższy cykl generowanych liczb pseudolosowych. Należy zatem losowane liczby sprowadzić do interesującego nas przedziału. Można to zrobić następująco (przez rand() oznaczymy przedstawiony wcześniej generator liczb pseudolosowych): a + (rand() mod (b-a+1)).

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 3
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 6
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 4
Tomasz LubińskiJava
.java
.java
***** / 3
 
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: 30 stycznia 2013 22:37
Dodaj komentarz