Generator Lehmera

Wstęp

Generator Lehmera to deterministyczny generator liczb pseudolosowych. Jest on szczególnym przypadkiem generatora LCG. Jego zaletą jest prostota implementacji. Jednak prostota niesie ze sobą pewną pułapkę. W tym artykule zostanie wyjaśnione jak z niego korzystać.

Opis Algorytmu

Idea

Każda kolejna wartość jest losowana na podstawie poprzedniej poprzez pomnożenie przez pewien mnożnik g z pewnego zakresu ograniczonego wartością n. Jest to szczególny przypadek generator LCG dla c = 0. Losowanie można opisać następującym wzorem:

x_{n + 1} = x_n·g mod n

Jak widać, aby skorzystać ze wzoru należy najpierw określić pewną wartość x₀ i już można generować kolejne wartości pseudolosowe. W takim generatorze dla tej samej wartości początkowej x zostanie otrzymany ten sam ciąg liczb.

Wartości ustalone

Jednak, aby algorytm mógł losować kolejne wartości należy określić mnożnik g i ograniczenie n. Istnieje wiele różnych propozycji par liczb dla tych wartości. Zostały one przedstawione poniżej:

Wartości g i n muszą zostać odpowiednio dobrane. Algorytm, choć bardzo prosty i zrozumiały, kryje w sobie niemiłą niespodziankę. Jeśli podczas działania algorytmu x·g = n to następną wartością będzie 0. Z kolei 0 pomnożone przez dowolną wartością zawsze będzie 0. Zatem istnieje możliwość, że od pewnego elementu ciąg losowanych liczb będzie samymi zerami.

W przypadku, gdy chcemy sami ustalić wartości g i n to należy pamiętać, że: n ma być liczbą pierwszą (lub wielkrotnością), g musi być pierwiastkiem pierwotnym modulo n, a wartość początkowa musi być względnie pierwsza z n.

Przykład

Przyjmując, że g = 75, a n = 2¹⁶ + 1 oraz wartość początkowa x₀ = 7 otrzyma się następujący ciąg liczb:

7, 525, 39375, 3960, 34852, 57957, 21333, 27087, 65415, ..

Taki algorytm można zastosować do stworzenia symulatora kostki sześciennej. Wtedy otrzymane wartości na każdym etapie możnaby konwertować na wartość:

2, 4, 4, 1, 5, 4, 4, 4, 4, 6, 2, 1, 2, 6, 3 ..

W tym przypadku zdecydowanie przeważałaby trafialność wartości 4, ale jak można zauważyć wszystkie wartości na kostce zostały uzyskane, więc pozostaje jedynie dobrać odpowiednie wartości. Rzecz jasna należy pamiętać, że jeśli g i n mają pozostać nienaruszone to należy przyjmować inną wartość początkową np. poprzez pobranie czasu.

Implementacja

Zaimplementowanie funkcji generującej ciąg liczb losowych polega na zwróceniu wyniku obliczonego według wzoru podanego wcześniej:

1. unsigned long generujLehmer(unsigned long x, unsigned long g = 75, unsigned long n = 65537) {
2.   return (g*x) % n;
3. }

Przyjmowane wartości muszą być tylko i wyłącznie dodatnie, ponieważ operacja modulo dla wartości ujemnych zwróci 0, więc może to spowodować niespodziewane problemu z losowaniem wartości. Domyślne wartości zostały ustawione na te znane z platformy Sinclair ZX81. Korzystając z napisanej funkcji generujLehmer() można napisać generator oparty na RANF:

1. unsigned long RANF(unsigned long x) {
2.   return generujLehmer(x, 44485709377909, 281474976710655);
3. }

Metodę RANF można znaleźć jako jedną z metod losowania liczb pseudolosowych w bilbiotece naukowej GNU.

Testowanie funkcji

Poniższy fragment kodu wczyta od użytkownika wartość początkową oraz ile liczb ma zostać wylosowanych:

1. int main() {
2.   unsigned long x;
3.   unsigned int k;
4.   cout << "Podaj wartosc poczatkowa\n x0 = ";
5.   cin >> x;
6.   cout << "Ile liczb wylosowac?\n n = ";
7.   cin >> k;
8.   cout << "Powstaly ciag:\n";
9.   while(k-- > 0) {
10.     cout << x << endl;
11.     x = generujLehmer(x);
12.   }
13.   system("pause");
14.   return 0;
15. }

• Kod źródłowy Implementacja