Generator liczb pseudolosowych LCG

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:

X n = ( a X n 1 + c ) m o d   m

Multiplikatywny LCG:

X n = a X n 1 m o d   m

Gdzie:

  • XIndeks dolny n - n‑ta liczba pseudolosowa,

  • XIndeks dolny n‑1  Indeks dolny koniec- 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 0.

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 0 = 0.

Przykładowe rozwiązanie

Aby wykonać poprawnie to zadanie, należy podstawić dane wartości a, c, m i XIndeks dolny 0 do wzoru. Otrzymamy w ten sposób wyrażenie:

X n = ( 4 X n 1 + 2 )   m o d   9

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.

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.

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.

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.

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.

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.

ziarno (ang. seed)
ziarno (ang. seed)

wartość inicjująca generator liczb pseudolosowych