Następny: Zadanie 2 - Statystyki opisowe W góre: Wybrane Zagadnienia Matematyki II Zadania do zaprogramowania Poprzedni: Wybrane Zagadnienia Matematyki II Zadania do zaprogramowania

Subsections

• Generator multiplikatywny liniowy kongruentny (MLCG)

Zadanie 1 - Generator liczb z rozkładu jednostajnego

Program generujący zadaną liczbę wartości pochodzących z rozkładu jednostajnego na odcinku [0,1] przy wykorzystaniu:

• algorytmu MLCG
• funkcji random dostępnej w danym języku programowania

Jeżeli nie jest to aplikacja konsolowa to program powinien posiadać możliwość zapisania wygenerowanych liczb do pliku tekstowego.

Generator multiplikatywny liniowy kongruentny (MLCG)

Generator oparty jest na zasadzie iteracyjnej:

$$x_{j+1}=(ax_j)\mod{m}$$ (1)

gdzie wszystkie wartości są liczbami całkowitymi. Wartość początkowa $x_0$ (seed) jest dowolną liczbą całkowitą z zakresu obejmującego okres generatora.
Algorytm (przenośny) Wichmanna, Hilla oraz L'Ecuaya: zakładamy, że mnożnik $a$ spełnia warunek $a^2 <m$ .
Definiujemy

$$q=m\: div \: a$$ (2)

oraz

$$r=m \:mod \:a$$ (3)

tak aby $m = aq+r$ , wówczas po przekształceniach otrzymujemy:

$$[ax] \:mod \: m=\left[a(x \: mod\: q) - (x \: div\: q )r\right]\mod{m}$$ (4)

gdzie wyrażenie w nawiasie zawiera się w przedziale $[-m,m]$ dla $x<m$ .
Stąd kolejne losowe liczby całkowite $x$ możemy wygenerować za pomocą algorytmu:

 k = x / q
 x = a * ( x - k * q ) - k * r
 if ( x < 0 ) then x = x + m

Wartości mnożnika $a$ oraz modułu $m$ muszą spełniać odpowiednie warunki aby zagwarantować dostatecznie długi okres liczb losowych.
Wartości $r$ i $q$ są stałymi obliczonymi według wzorów (2,3).
W poniższej tabeli zawartych jest kilka właściwych wartości dla maszyny 32 bitowej (S. Brandt):

m	a
2147483647	39373
2147483563	40014
2147483399	40692

Okres całego szeregu wynosi $m-1$ , algorytm jest przenośny gdyż wszystkie obliczenie są dokonywane w arytmetyce liczb całkowitych.
Chcąc otrzymać liczby zmiennopozycyjne z zakresu $[0,1]$ należy wynik podzielić przez $m$ .

Następny: Zadanie 2 - Statystyki opisowe W góre: Wybrane Zagadnienia Matematyki II Zadania do zaprogramowania Poprzedni: Wybrane Zagadnienia Matematyki II Zadania do zaprogramowania