Generatory liczb pseudolosowych

Liczby pseudolosowe

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.

 

Generatory LCG

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 m - 1. Z pierwszej i drugiej własności wynika, iż po m cyklach obliczeniowych, liczby pseudolosowe zaczynają się powtarzać:

 

X0X1X2 → ...  → Xm-2  → Xm-1X0X1 → ...

 

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 m - 1, a generator multiplikatywne generuje je z zakresu od 1 do m - 1. Poniżej podajemy prosty algorytm doboru współczynników dla generatora LCG.

 

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 a - 1 również powinno być podzielne przez 4.

 

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


Generator LCG
(C)2012 mgr Jerzy Wałaszek

m = , a = , c = , X0 =


...

 

Własności generatorów LCG

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 (a × Xn-1 + c) i wynik umieszcza w 32-bitowym obszarze pamięci, co powoduje automatyczne obcięcie bitów wykraczających poza 31-szą pozycję.

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  

 

Liczby pseudolosowe w przedziale

Problem

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 - np. m = 264. Następnie wygenerowaną liczbę pseudolosową dzielimy przez 6 i bierzemy resztę z tego dzielenia. Otrzymamy liczby od 0 do 5. Sekwencje tych liczb będą się powtarzały z okresem 264! (przynajmniej teoretycznie jeśli 6 nie dzieli modułu generatora!) Aby sprowadzić wynik do przedziału <1,6> musimy do otrzymanej reszty dodać 1.

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:

 

Lxyy - 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):

 

XRX : 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.

 

Algorytm generacji liczb pseudolosowych

Wejście
x, y    początek i koniec przedziału generacji liczb pseudolosowych, x,y C
LCG(m,a,c)  – generator LCG
Wyjście:

Wxy liczba pseudolosowa z przedziału <x,y>.

Elementy pomocnicze:
Lxy    długość przedziału <x,y> + 1
X  – ziarno pseudolosowe oraz liczba pseudolosowa
XR  – rzeczywista liczba pseudolosowa z przedziału <0,1)
Lista kroków:
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:     Lxyy - 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  

Generacja liczb pseudolosowych w Code::Blocks

Inicjalizacja

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 srand(time(NULL)) wewnątrz pętli tworzącej kolejne liczby pseudolosowe – efekt będzie wręcz odwrotny do zamierzonego. Zobacz na podobny przykład w Pascalu!

 

Generacja całkowitych liczb pseudolosowych

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

 

Generacja rzeczywistych liczb pseudolosowych

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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.