Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2013 mgr
Jerzy Wałaszek
|
Liczba losowa (ang. random number) jest liczbą r należącą do pewnego zbioru wartości {r1, ..., rn} wybieranych z pewnym prawdopodobieństwem. Jeśli jako r może pojawić się każda z liczb zbioru z tym samym prawdopodobieństwem p(r) = 1/n, to mówimy o równomiernym rozkładzie prawdopodobieństwa liczb losowych z tego zbioru. Na przykład rozważmy rzut kostką. Każdy rzut daje liczbę losową r ze zbioru {1,2,3,4,5,6}. Jeśli kostka nie jest oszukana, to każda z możliwych wartości r pojawia się w rzucie kostką z prawdopodobieństwem p(r) = 1/6. Liczby losowe r posiadają zatem równomierny rozkład prawdopodobieństwa.
Problem z otrzymaniem liczb losowych wynika z deterministycznego charakteru komputera i wykonywanych przez niego operacji. Gdy człowiek dokonuje rzutu kością, nie wie co wypadnie. Taka sama operacja na komputerze wymaga działania, którego wynik jest nieprzewidywalny – żadna z operacji wykonywanych przez procesor nie posiada takiej cechy (o ile procesor jest sprawny). Problem starano się rozwiązać wykorzystując zewnętrzne źródła sygnałów losowych (np. generatory białego szumu), jednakże w tego typu urządzenia nie są standardowo wyposażano komputery osobiste – należałoby wspomnieć o próbach wykorzystania szumów kart graficznych, jednakże system ten nie rozpowszechnił się z prostej przyczyny – różne karty dźwiękowe szumią różnie, a te z górnej półki nie szumią prawie wcale.
Z drugiej strony liczby losowe używane są powszechnie przy programowaniu komputerów – gry losowe, symulacje różnych procesów losowych, statystycznych, testowanie algorytmów dla losowych zestawów danych itp. Ponieważ nie możemy w prosty sposób mieć prawdziwych liczb losowych, musimy się zadowolić ich sztucznym odpowiednikiem – liczbami pseudolosowymi (ang. pseudorandom numbers). Liczby pseudolosowe wyglądają jak losowe, lecz tworzy się je algorytmicznie. Oznacza to, iż znając wzór generacyjny oraz kilka kolejnych liczb pseudolosowych możemy bez problemu wygenerować wszystkie dalsze – tej cechy nie posiadają liczby losowe, w przeciwnym razie totolotek straciłby sens.
Do rozwiązania problemu generacji liczb pseudolosowych opracowano specjalne funkcje modularne zwane liniowymi generatorami kongruencyjnymi liczb pseudolosowych (ang. pseudorandom number linear congruential generator – w skrócie LCG) o następującej postaci:
Xn
= (a × Xn-1 + c)
mod m |
|
Xn | – n-ta liczba pseudolosowa |
Xn-1 | – poprzednia liczba pseudolosowa |
a | – mnożnik |
c | – przyrost |
m | – moduł |
Ze wzoru wynika, iż kolejna liczba pseudolosowa Xn powstaje z poprzedniej Xn-1. Liczby te tworzą zatem ściśle określony ciąg kolejno następujących po sobie wartości.
Drugą cechą charakterystyczną jest to, iż liczba pseudolosowa
Xn jest resztą z dzielenia przez moduł m. Skoro tak,
to może przyjmować wartości od 0 do
X0 → X1 → X2 → ... → Xm-2 → Xm-1 → X0 → X1 → ...
Jeśli współczynniki a, c i m są źle dobrane, to cykl powtarzania może być krótszy niż m.
Rozróżniamy dwa podstawowe rodzaje generatorów LCG:
Addytywny LCG: | Xn = (aXn-1 + c) mod m |
Multiplikatywny LCG: | Xn = aXn-1 mod m |
Podstawowa różnica pomiędzy nimi jest taka, iż generator
addytywny LCG może generować liczby pseudolosowe z zakresu od 0 do
Określamy zakres liczb pseudolosowych 0...Xmax (dla LCG multiplikatywnego jest to 1...Xmax). Moduł m jest zawsze o 1 większy od maksymalnej liczby w zakresie, czyli:
m = Xmax + 1
Przyrost c musi być względnie pierwszy z modułem m. Możemy m rozłożyć na czynniki pierwsze i dla c wybieramy czynniki nie występujące w m. Możemy również generować pseudolosowe c i sprawdzać, czy spełnia warunek:
NWD(c,m) = 1
Mnożnik dobieramy wykorzystując regułę, iż wyrażenie a
- 1 jest podzielne przez każdy czynnik pierwszy modułu m. Jeśli moduł
m dzieli się przez 4, to
Przykład:
Zaprojektować addytywny generator LCG generujący liczby pseudolosowe w przedziale od 0 do 11.
Z warunków zadania mamy:
Xmax = 11
m = Xmax + 1 = 11 + 1 = 12
Przyrost c musi być względnie pierwszy z m. Moduł m rozkładamy na iloczyn czynników pierwszych:
m = 2 × 2 × 3
Na przyrost c możemy wybrać dowolną liczbę nie posiadającą czynników 2 i 3. Na przykład może to być:
c = 7
Wyrażenie a - 1 musi być podzielne przez 4 i 3.
a - 1 = 4 × 3 = 12
a = 12 + 1 = 13
Otrzymujemy następujący wzór generatora LCG: Xn = (13 × Xn-1 + 7) mod 12 → LCG(12,13,7)
Ponieważ wzór ten pozwala obliczyć kolejną liczbę pseudolosową Xn z liczby poprzedniej Xn-1, musimy określić wartość startową X0, od której rozpocznie się generacja liczb pseudolosowych. Wartość tę nazywamy ziarnem pseudolosowym (ang. pseudorandom seed). Ziarno wpływa na miejsce w pierścieniu liczb pseudolosowych, od którego rozpocznie się generacja następnych liczb.
Przyjmijmy X0 = 0 i policzmy wszystkie kolejne liczby pseudolosowe, które tworzy nasz generator LCG:
X1 = 13 × | 0 + 7 mod 12 = | 7 mod 12 = | 7 | |
X2 = 13 × | 7 + 7 mod 12 = | 98 mod 12 = | 2 | |
X3 = 13 × | 2 + 7 mod 12 = | 33 mod 12 = | 9 | |
X4 = 13 × | 9 + 7 mod 12 = | 124 mod 12 = | 4 | |
X5 = 13 × | 4 + 7 mod 12 = | 59 mod 12 = | 11 | |
X6 = 13 × | 11 + 7 mod 12 = | 150 mod 12 = | 6 | |
X7 = 13 × | 6 + 7 mod 12 = | 85 mod 12 = | 1 | |
X8 = 13 × | 1 + 7 mod 12 = | 20 mod 12 = | 8 | |
X9 = 13 × | 8 + 7 mod 12 = | 111 mod 12 = | 3 | |
X10 = 13 × | 3 + 7 mod 12 = | 46 mod 12 = | 10 | |
X11 = 13 × | 10 + 7 mod 12 = | 137 mod 12 = | 5 | |
X12 = 13 × | 5 + 7 mod 12 = | 72 mod 12 = | 0 | |
X13 = 13 × | 0 + 7 mod 12 = | 7 mod 12 = | 7 | = X1 – ciąg zaczyna się powtarzać |
X14 = 13 × | 7 + 7 mod 12 = | 98 mod 12 = | 2 | = X2 |
... |
Dla X0 = 0 otrzymaliśmy ciąg liczb pseudolosowych: 7 2 9 4 11 6 1 8 3 10 5 0 7 2 9 4 ...
Jeśli przyjmiemy inną wartość za X0, to otrzymamy ten sam ciąg, lecz startujący od innego punktu:
Dla X0 = 1 mamy : 8 3 10 5 0 7 2 9 4 11 6 1 ...
Dla X0 = 2 mamy : 9 4 11 6 1 8 3 10 5 0 7 2 ...
Dla X0 = 3 mamy : 10 5 0 7 2 9 4 11 6 1 8 3 ...
Następstwo kolejnych liczb pseudolosowych jest zawsze takie samo – np. po liczbie 3 zawsze wystąpi liczba 10.
Z powyższych rozważań można wyciągnąć wniosek, iż każdy generator LCG da się jednoznacznie scharakteryzować czwórką parametrów:
LCG(m,a,c,X0)
m – moduł
a – mnożnik
c – przyrost
X0 – ziarno
W praktycznych realizacjach dąży się do dużych okresów generatora LCG – wtedy liczby pseudolosowe powtarzają się dopiero po wielu miliardach przebiegów. Jako przykład niech posłuży poniższy generator LCG zaproponowany przez prof. D. Knutha:
LCG(34359738368, 3141592653, 2718281829, Xo)
m = 34359738368 = 235
a = [π × 109]
c = [e × 109], e –
podstawa logarytmów naturalnych, e =
2,7182818284590452353602874713527...
Generatory LCG zostały opracowane dosyć dawno i dzisiaj są już nieco przestarzałe. Posiadają szereg istotnych wad, dlatego nie powinno się ich stosować w aplikacjach, gdzie wymagana jest wysoka przypadkowość danych – np. losowania w grach liczbowych, symulacje ekonomiczne i finansowe, profesjonalne systemy kryptograficzne itp. Natomiast dla potrzeb amatorskich są zupełnie wystarczające ze względu na swoją prostotę – dlatego opisujemy je w naszym serwisie.
Jednym z poważnych problemów generatorów LCG jest to, iż młodsze bity generowanych liczb pseudolosowych posiadają krótszy okres powtarzania niż cała liczba pseudolosowa, jeśli moduł jest potęgą liczby 2 - a tak zwykle jest we wbudowanych generatorach LCG z uwagi na prostotę wyliczania reszty z dzielenia przez moduł, gdzie dzielenie zastępuje się obcinaniem bitów wykraczających poza wartość modułu:
Jeśli m = 2k, to
Xn = (a × Xn-1 + c) mod 2k = (a × Xn-1 + c) obcięte do k bitów.
Najczęściej k = 16 lub 32, co daje wynik
bezpośrednio mieszczący się w komórkach pamięci. Procesor wylicza wyrażenie
Poniżej podajemy przykładowe parametry generatorów LCG stosowanych w różnych językach programowania (źródło pochodzi z Wikipedii):
Źródło | m | a | c | Wyjściowe bity ziarna w rand() lub w Random(L) |
---|---|---|---|---|
Numerical Recipes | 232 | 1664525 | 1013904223 | |
Borland C/C++ | 232 | 22695477 | 1 | bity 30..16 w rand(), 30..0 w lrand() |
GNU Compiler Collection | 232 | 69069 | 5 | bity 30..16 |
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ | 232 | 1103515245 | 12345 | bity 30..16 |
Borland Delphi, Virtual Pascal | 232 | 134775813 | 1 | bity 63..32 w (seed * L) |
Microsoft Visual/Quick C/C++ | 232 | 214013 | 2531011 | bity 30..16 |
ANSIC | 231 | 1103515245 | 12345 | |
MINSTD | 231-1 | 16807 | 0 | |
RANDU | 231 | 65539 | 0 | |
SIMSCRIPT | 231-1 | 630360016 | 0 | |
BCSLIB | 235 | 515 | 7261067085 | |
BCPL | 232 | 2147001325 | 715136305 | |
URN12 | 231 | 452807053 | 0 | |
APPLE | 235 | 1220703125 | 0 | |
Super-Duper | 232 | 69069 | 0 |
Mając dany generator LCG należy wygenerować serie liczb pseudolosowych w przedziale całkowitym <x,y>.
Jest to typowe zadanie losowania wartości pseudolosowej. Załóżmy, iż tworzymy program gry w kości. W grze będziemy losować wyniki rzutów kostką będące liczbami pseudolosowymi z przedziału całkowitego <1,6>. Na pierwszy rzut oka wygląda na to, iż problem rozwiążemy tworząc generator LCG generujący liczby od 1 do 6 (może to być generator multiplikatywny). Odradzam to rozwiązanie – okres powtarzania takiego generatora jest bardzo krótki i ze względu na własności generatorów LCG po każdych 6 rzutach kostką otrzymywalibyśmy wciąż te same wyniki – przyznasz, że gra straciłaby wiele na atrakcyjności.
Problem rozwiązujemy inaczej – tworzony jest generator LCG o
bardzo dużym okresie m
Zapiszmy to tak:
X ← (a × X + c) mod
m
W ← (X mod 6) + 1
X | – liczba pseudolosowa |
m,a,c | – współczynniki generatora LCG |
W | – wynik losowania rzutu kostką |
Powyższy wzór możemy w prosty sposób uogólnić na dowolny przedział całkowity <x,y>. W tym celu obliczamy długość przedziału plus jeden:
Lxy ← y - x + 1
Liczba Lxy stanie się dzielnikiem wygenerowanej przez generator liczby pseudolosowej X. Otrzymaną z dzielenia resztę należy zwiększyć o wartość x, aby wpadała w przedział <x,y>:
Wxy ← (X mod Lxy) + x
Otrzymane w powyższy sposób liczby pseudolosowe mogą cierpieć na zmniejszoną pseudolosowość młodszych bitów w liczbach generowanych przez generator LCG. Istnieje proste i w miarę skuteczne rozwiązanie tego problemu. Liczbę X dzielimy przez m zmiennoprzecinkowo i zapamiętujemy wynik, który jest rzeczywistą liczbą pseudolosową z przedziału <0,1):
XR ← X : m
Następnie liczbę XR wymnażamy przez Lxy i jako wynik bierzemy część całkowitą tego iloczynu powiększoną o x:
Wxy ← [XR × Lxy] + x
Ponieważ teraz przy tworzeniu Wxy są brane pod uwagę wszystkie bity X (a nie tylko te młodsze z reszty z dzielenia, które mają niską przypadkowość), wynik jest "bardziej" pseudolosowy niż w pierwszym rozwiązaniu.
Pozostaje jeszcze jeden, bardzo istotny problem. Generator LCG startując od zadanego ziarna X0 zawsze tworzy ten sam ciąg liczb pseudolosowych. Wynika z tego, iż nasz program powinien przy każdym uruchomieniu wybierać inne ziarno, w przeciwnym razie wylosowane liczby będą się powtarzały – np. zawsze gracze będą wyrzucali te same sekwencje oczek lub będą otrzymywali te same kolejne układy kart w grach losowych przy każdym uruchomieniu programu – w końcu nauczą się ich na pamięć!. W komputerach IBM-PC mamy do dyspozycji tzw. zegar czasu rzeczywistego (ang. RTC – Real Time Clock), który zlicza czas – dzięki niemu komputer IBM-PC utrzymuje poprawną datę i czas systemowy. Czas zliczany jest z dokładnością do milisekund. Przy każdym uruchomieniu programu odczytujemy stan zegara i wykorzystujemy go jako wartość dla ziarna pseudolosowego generatora LCG. W ten sposób ziarno jest każdorazowo inne (nie wiadomo przecież z góry, w jakim czasie użytkownik będzie uruchamiał swój program), zatem sekwencja liczb pseudolosowych wystartuje od innego punktu. W efekcie otrzymamy nieprzewidywalne z góry ciągi pseudolosowe – i o to właśnie chodzi.
x, y | – | początek i koniec przedziału generacji liczb pseudolosowych, x,y C |
LCG(m,a,c) | – | generator LCG |
Wxy liczba pseudolosowa z przedziału <x,y>.
Lxy | – | długość przedziału <x,y> + 1 |
X | – | ziarno pseudolosowe oraz liczba pseudolosowa |
XR | – | rzeczywista liczba pseudolosowa z przedziału <0,1) |
K01: | X ← czas z zegara RTC | ; tworzymy przypadkowe ziarno generatora LCG |
K02: | Powtarzaj wymaganą liczbę razy kroki K03...K07 | ; w pętli generujemy pożądaną ilość liczb pseudolosowych |
K03: | X ← (a × X + c) mod m | ; generujemy liczbę pseudolosową |
K04: | XR ← X : m | ; tworzymy rzeczywistą liczbę pseudolosową |
K05: | Lxy ← y - x + 1 | ; obliczamy długość przedziału <x,y> plus 1 |
K06: | Wxy ← ⌊XR × Lxy⌋ + x | ; obliczamy liczbę pseudolosową w <x,y> |
K07: | Przetwarzaj Wxy | ; wykorzystujemy wygenerowaną liczbę pseudolosową |
K08: | Zakończ |
Generator pseudolosowy jest inicjowany za pomocą funkcji:
srand(x0);
Funkcja srand() wymaga dołączenia pliku nagłówkowego cstdlib. Argument x0 zostanie użyty jako ziarno generacji liczb pseudolosowych. Oby otrzymywać w programach bardziej losowe ciągi liczb pseudolosowych, generator inicjujemy wybraną wartością losową, np. wynikiem funkcji time(), który zmienia się co sekundę. Funkcja time() wymaga dołączenia pliku nagłówkowego time.h. Na początku programu umieszczamy następujące wywołanie:
... srand((unsigned)time(NULL)); ...
Ponieważ czas jest zliczany niezależnie od procesów obliczeniowych komputera, nie wiadomo, w którym momencie program zostanie uruchomiony i wywołana będzie funkcja time(). Dlatego jej wynik możemy potraktować jako losowy. Wpisanie go do ziarna generatora pseudolosowego spowoduje generowanie innej sekwencji liczb pseudolosowych przy każdym uruchomieniu programu.
Inicjalizację generatora pseudolosowego wykonujemy tylko jeden
raz, zawsze na początku programu, przed generacją liczb pseudolosowych. Nie ma
sensu umieszczanie wywołania funkcji
Dostęp do kolejnych liczb pseudolosowych uzyskujemy za pomocą funkcji rand(), która zwraca wygenerowaną przez generator liczbę pseudolosową z zakresu od 0 do RAND_MAX (stała RAND_MAX zdefiniowana jest w pliku nagłówkowym cstdlib i ma wartość 32767 = 215 - 1). Funkcja rand() nie zwraca całej liczby pseudolosowej, tylko jej górne 15 bitów. Takie rozwiązanie przyjęto dlatego, iż okazuje się, że generatory LCG generują młodsze bity z mniejszymi okresami powtarzania niż okresy bitów starszych. Zwracanie starszych bitów po części niweluje tę wadę.
Jeśli wystarcza nam 15 bitowy zakres liczb pseudolosowych, to do generacji liczby pseudolosowej w przedziale <a,b> stosujemy prosty wzór:
a + rand() % (b - a + 1)
Lepszym rozwiązaniem będzie sprowadzenie wyniku rand() do wartości zmiennoprzecinkowej w przedziale <0,1>, a następnie wykorzystanie tej wartości do generacji liczby pseudolosowej w przedziale całkowitym <a,b>.
a + (int)(((double)rand() / (double)RAND_MAX) * (b - a))
Jeśli potrzebujemy większego zakresu liczb pseudolosowych niż 15 bitów, to możemy wykorzystać funkcję rand() kilkakrotnie:
16 bitów: |
(rand() | (rand() << 15)) & 0xFFFF |
20 bitów: |
(rand() | (rand() << 15)) & 0xFFFFF |
24 bity: |
(rand() | (rand() << 15)) & 0xFFFFFF |
32 bity: |
(rand() | (rand() << 15) | (rand() << 30)) & 0xFFFFFF |
Do generacji rzeczywistych liczb pseudolosowych wynik funkcji rand() sprowadzamy do przedziału {0...1}, a następnie otrzymaną wartość wykorzystujemy do uzyskania rzeczywistej liczby pseudolosowej. Poniżej podajemy prosty sposób realizacji tego zadania.
<0,1) |
: (double)rand() / (double)(RAND_MAX + 1) |
<0,1> |
: (double)rand() / (double)(RAND_MAX) |
(0,1> |
: 1 - (double)rand() / (double)(RAND_MAX + 1) |
(0,1) |
: (double)(1 + rand()) / (double)(RAND_MAX + 2) |
Rzeczywistą liczbę pseudolosową z przedziału {0...1} wykorzystujemy do generacji liczby pseudolosowej w przedziale {a...b} następująco:
a + liczba_pseudolosowa{0...1} * (b - a)
Na przykład chcemy wygenerować liczbę pseudolosową w przedziale od a = 2.5 do b = 4.0 włącznie. Przedział ma być domknięty, zatem potrzebujemy liczby pseudolosowej z przedziału domkniętego <0,1>. Wzór jest następujący:
2.5 + (double)rand() / (double)(RAND_MAX) * 1.5
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe