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. def generujLehmer(x, g = 75, n = 65537):
2.   return (g*x) % n

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. def RANF(x):
2.   return generujLehmer(x, 44485709377909, 281474976710655)

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. x = int(input("Podaj wartość początkową\n x0 = "))
2. k = int(input("Ile liczb wypisać?\n k = "))
3. print("Powstały ciąg:\n")
4. while(k > 0):
5.   print(x)
6.   x = generujLehmer(x)
7.   k -= 1

• Kod źródłowy Implementacja