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. static ulong generujLehmer(ulong x, ulong g = 75, ulong 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. static ulong RANF(ulong 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. static void Main(string[] args) {
2.   Console.Write("Podaj wartość początkową\n x0 = ");
3.   ulong x = Convert.ToUInt64(Console.ReadLine());
4.   Console.Write("Ile liczb wylosować?\n k = ");
5.   uint k = Convert.ToUInt32(Console.ReadLine());
6.   Console.WriteLine("Powstały ciąg:");
7.   while (k-- > 0) {
8.     Console.WriteLine(x);
9.     x = generujLehmer(x);
10.   }
11.   Console.ReadKey();
12. }

• Kod źródłowy Implementacja