Generator LCG jest jednym z algorytmów służących do obliczania wartości pseudolosowych. Wykorzystywane są w nim funkcje modularnearytmetyka modularnafunkcje modularne zwane liniowymi generatorami kongruencyjnymi liczb pseudolosowych (ang. pseudorandom number linear congruential generator – w skrócie LCG).
Można wyróżnić dwa podstawowe wzory do obliczania liczb pseudolosowych z wykorzystaniem generatora LCG.
Addytywny LCG:
Multiplikatywny LCG:
Gdzie:
XIndeks dolny nn - n‑ta liczba pseudolosowa,
XIndeks dolny n‑1 Indeks dolny koniecn‑1 - poprzednia liczba pseudolosowa,
a - mnożnik,
c - parametr, dla generatora multiplikatywnego c = 0,
m - ilość liczb generowanych.
Liczby wygenerowane przez addytywny LCG mogą przyjmować wartości z przedziału od 0 do m‑1, zaś multiplikatywny z przedziału od 1 do m‑1. Po m wykonaniach wartości zaczynają się powtarzać, wynika to z własności działania modulo.
Konieczne jest podanie wartości oznaczającej ziarno (ang. seed) będące początkową wartością XIndeks dolny 00.
Aby generator działał poprawnie, wartości a, c i m nie mogą być przypadkowe. Muszą zostać dobrane zgodnie z poniższymi zasadami:
wartość zmiennej m jest o jeden większa od największej wartości losowej, jaką algorytm będzie mógł wygenerować;
parametr c musi być względnie pierwszy z m;
wartość wyrażenia a‑1 jest wielokrotnością wszystkich dzielników zmiennej m.
Zadanie 1.
Wypisz kolejnych 18 wartości, jakie będzie generował addytywny generator LCG dla podanych danych:
a = 4,
c = 2,
m = 9,
XIndeks dolny 00 = 0.
Przykładowe rozwiązanie
Aby wykonać poprawnie to zadanie, należy podstawić dane wartości a, c, m i XIndeks dolny 00 do wzoru. Otrzymamy w ten sposób wyrażenie:
Następnie wystarczy tylko obliczać kolejne wartości zgodnie z podanym wzorem. Łatwo można zaobserwować, że gdy zostanie wypisana wartość 0 algorytm „zapętla się” i wraca.
Linia 1. Xn znak równości otwórz nawias okrągły 4 asterysk Xn minus 1 plus 2 zamknij nawias okrągły mod 9.
Linia 3. X0 znak równości otwórz nawias okrągły 4 asterysk 0 plus 2 zamknij nawias okrągły mod 9 znak równości 2 mod 9 znak równości 2.
Linia 4. X1 znak równości otwórz nawias okrągły 4 asterysk 2 plus 2 zamknij nawias okrągły mod 9 znak równości 10 mod 9 znak równości 1.
Linia 5. X2 znak równości otwórz nawias okrągły 4 asterysk 1 plus 2 zamknij nawias okrągły mod 9 znak równości 6 mod 9 znak równości 6.
Linia 6. X3 znak równości otwórz nawias okrągły 4 asterysk 6 plus 2 zamknij nawias okrągły mod 9 znak równości 26 mod 9 znak równości 8.
Linia 7. X4 znak równości otwórz nawias okrągły 4 asterysk 8 plus 2 zamknij nawias okrągły mod 9 znak równości 34 mod 9 znak równości 7.
Linia 8. X5 znak równości otwórz nawias okrągły 4 asterysk 7 plus 2 zamknij nawias okrągły mod 9 znak równości 30 mod 9 znak równości 3.
Linia 9. X6 znak równości otwórz nawias okrągły 4 asterysk 3 plus 2 zamknij nawias okrągły mod 9 znak równości 14 mod 9 znak równości 5.
Linia 10. X7 znak równości otwórz nawias okrągły 4 asterysk 5 plus 2 zamknij nawias okrągły mod 9 znak równości 22 mod 9 znak równości 4.
Linia 11. X8 znak równości otwórz nawias okrągły 4 asterysk 4 plus 2 zamknij nawias okrągły mod 9 znak równości 18 mod 9 znak równości 0.
Linia 12. X9 znak równości otwórz nawias okrągły 4 asterysk 0 plus 2 zamknij nawias okrągły mod 9 znak równości 2 mod 9 znak równości 2.
Linia 13. X10 znak równości otwórz nawias okrągły 4 asterysk 2 plus 2 zamknij nawias okrągły mod 9 znak równości 10 mod 9 znak równości 1.
Linia 14. X11 znak równości otwórz nawias okrągły 4 asterysk 1 plus 2 zamknij nawias okrągły mod 9 znak równości 6 mod 9 znak równości 6.
Linia 15. X12 znak równości otwórz nawias okrągły 4 asterysk 6 plus 2 zamknij nawias okrągły mod 9 znak równości 26 mod 9 znak równości 8.
Linia 16. X13 znak równości otwórz nawias okrągły 4 asterysk 8 plus 2 zamknij nawias okrągły mod 9 znak równości 34 mod 9 znak równości 7.
Linia 17. X14 znak równości otwórz nawias okrągły 4 asterysk 7 plus 2 zamknij nawias okrągły mod 9 znak równości 30 mod 9 znak równości 3.
Linia 18. X15 znak równości otwórz nawias okrągły 4 asterysk 3 plus 2 zamknij nawias okrągły mod 9 znak równości 14 mod 9 znak równości 5.
Linia 19. X16 znak równości otwórz nawias okrągły 4 asterysk 5 plus 2 zamknij nawias okrągły mod 9 znak równości 22 mod 9 znak równości 4.
Linia 20. X17 znak równości otwórz nawias okrągły 4 asterysk 4 plus 2 zamknij nawias okrągły mod 9 znak równości 18 mod 9 znak równości 0.
Xn = (4 * Xn-1 + 2) mod 9
X0 = (4 * 0 + 2) mod 9 = 2 mod 9 = 2
X1 = (4 * 2 + 2) mod 9 = 10 mod 9 = 1
X2 = (4 * 1 + 2) mod 9 = 6 mod 9 = 6
X3 = (4 * 6 + 2) mod 9 = 26 mod 9 = 8
X4 = (4 * 8 + 2) mod 9 = 34 mod 9 = 7
X5 = (4 * 7 + 2) mod 9 = 30 mod 9 = 3
X6 = (4 * 3 + 2) mod 9 = 14 mod 9 = 5
X7 = (4 * 5 + 2) mod 9 = 22 mod 9 = 4
X8 = (4 * 4 + 2) mod 9 = 18 mod 9 = 0
X9 = (4 * 0 + 2) mod 9 = 2 mod 9 = 2
X10 = (4 * 2 + 2) mod 9 = 10 mod 9 = 1
X11 = (4 * 1 + 2) mod 9 = 6 mod 9 = 6
X12 = (4 * 6 + 2) mod 9 = 26 mod 9 = 8
X13 = (4 * 8 + 2) mod 9 = 34 mod 9 = 7
X14 = (4 * 7 + 2) mod 9 = 30 mod 9 = 3
X15 = (4 * 3 + 2) mod 9 = 14 mod 9 = 5
X16 = (4 * 5 + 2) mod 9 = 22 mod 9 = 4
X17 = (4 * 4 + 2) mod 9 = 18 mod 9 = 0
Zadanie 2.
Uzupełnij tabelę tak, aby przy pomocy podanych danych algorytm działał poprawnie. Wypisz współczynniki o następujących właściwościach:
największa liczba, jaka może zostać wylosowana - Xmax,
współczynnik m o najwyższej możliwej wartości,
minimalna wartość współczynnika a,
wartości, jakich współczynnik c nie może przyjąć.
Xmax
maksymalna wartość zmiennej m
minimalna wartość zmiennej a
wartości jakich nie może przyjąć zmienna c
10
30
51
209
5
Przykładowe rozwiązanie
a) Xmax = 10
Linia 1. m znak równości Xmax plus 1 znak równości 10 plus 1 znak równości 11.
Linia 2. a minus 1 znak równości 11.
Linia 4. Naturalnie a minus 1 może być inną liczbą podzielną przez 11 przecinek ale w zadaniu wybieramy najmniejsze współczynniki.
Linia 6. a znak równości 11 plus 1 znak równości 12.
Linia 8. Wartość m znak równości 11 jest liczbą pierwszą przecinek więc wartość zmiennej c może być wszystkim poza 11 kropka.
m = Xmax + 1 = 10 + 1 = 11
a - 1 = 11
Naturalnie a - 1 może być inną liczbą podzielną przez 11, ale w zadaniu wybieramy najmniejsze współczynniki
a = 11 + 1 = 12
Wartość m = 11 jest liczbą pierwszą, więc wartość zmiennej c może być wszystkim poza 11.
b) m = 30
Linia 1. Xmax znak równości m minus 1 znak równości 30 minus 1 znak równości 29.
Linia 3. m znak równości 2 asterysk 3 asterysk 5.
Linia 5. a minus 1 znak równości 30.
Linia 6. a znak równości 30 plus 1 znak równości 31.
Linia 8. c nie może być równa 2 przecinek 3 ani 5.
Xmax = m - 1 = 30 - 1 = 29
m = 2 * 3 * 5
a - 1 = 30
a = 30 + 1 = 31
c nie może być równa 2, 3 ani 5
c) a = 51
Linia 1. a minus 1 znak równości 50.
Linia 2. 50 znak równości 2 asterysk 5 asterysk 5.
Linia 4. Liczba 50 musi być wielokrotnością liczby m przecinek więc m może być równe 2 przecinek 5 przecinek 10 przecinek 25 lub 50 kropka Wybieramy największą wartość przecinek czyli 50 kropka.
Linia 6. m znak równości 50.
Linia 8. Xmax znak równości m minus 1 znak równości 50 minus 1 znak równości 49.
Linia 10. c może przyjąć każdą wartość poza 2 i 5.
a - 1 = 50
50 = 2 * 5 * 5
Liczba 50 musi być wielokrotnością liczby m, więc m może być równe 2, 5, 10, 25 lub 50. Wybieramy największą wartość, czyli 50.
m = 50
Xmax = m - 1 = 50 - 1 = 49
c może przyjąć każdą wartość poza 2 i 5
d) Xmax = 209
Linia 1. m znak równości Xmax plus 1 znak równości 210.
Linia 2. 210 znak równości 2 asterysk 3 asterysk 5 asterysk 7.
Linia 4. a znak równości 211.
Linia 6. c nie może być równe 2 przecinek 3 przecinek 5 ani 7.
m = Xmax + 1 = 210
210 = 2 * 3 * 5 * 7
a = 211
c nie może być równe 2, 3, 5 ani 7
Rozwiązanie zadania:
Xmax
maksymalna wartość zmiennej m
minimalna wartość zmiennej a
wartości jakich nie może przyjąć zmienna c
10
11
12
11
29
30
31
2, 3, 5
49
50
51
2, 5
209
210
211
2, 3, 5, 7
Słownik
arytmetyka modularna
arytmetyka modularna
działanie polegające na obliczeniu reszty z dzielenia danej liczby przez inną wartość
liczby względnie pierwsze
liczby względnie pierwsze
liczby, które w rozkładzie na czynniki pierwsze nie mają żadnego wspólnego dzielnika; przykładem liczb względnie pierwszych jest 15 i 8.