Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

Pomoce:

Liczby pseudolosowe

Liczba losowa (ang. random number) jest liczbą r  należącą do pewnego zbioru wartości {r₁, ..., r_n} 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) = ¹/_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) = ¹/₆. 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. Dlatego osiągane wyniki nie były jednakowe i pomysł zarzucono.

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:

Ze wzoru wynika, iż kolejna liczba pseudolosowa X_n powstaje z poprzedniej X_n-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 X_n  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ć:

X₀ → X₁ → X₂ → ...  → X_m-2  → X_m-1 → X₀ → X₁ → ...

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:

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...X_max (dla LCG multiplikatywnego jest to 1...X_max). Moduł m  jest zawsze o 1 większy od maksymalnej liczby w zakresie, czyli:

m  = X_max  + 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:

X_max  = 11
m  = X_max  + 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:    X_n  = (13 × X_n-1 + 7) mod 12   → LCG(12,13,7)

Ponieważ wzór ten pozwala obliczyć kolejną liczbę pseudolosową X_n  z liczby poprzedniej X_n-1, musimy określić wartość startową X₀, 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 X₀ = 0 i policzmy wszystkie kolejne liczby pseudolosowe, które tworzy nasz generator LCG:

Dla X₀ = 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 X₀, to otrzymamy ten sam ciąg, lecz startujący od innego punktu:

Dla X₀ = 1 mamy : 8 3 10 5 0 7 2 9 4 11 6 1 ...
Dla X₀ = 2 mamy : 9 4 11 6 1 8 3 10 5 0 7 2 ...
Dla X₀ = 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,X₀)
m  - moduł
a  - mnożnik
c  - przyrost
X₀ - 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, X_o)

m  = 34359738368 = 2³⁵
a  = [π  × 10⁹]
c  = [e  × 10⁹],  e  - podstawa logarytmów naturalnych, e  = 2,7182818284590452353602874713527...

Program generujący ciąg liczb pseudolosowych

// Generator liczb pseudolosowych
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned m,a,c,X0,i;

    cout << "m = "; cin >> m;
    cout << "a = "; cin >> a;
    cout << "c = "; cin >> c;
    cout << "X0= "; cin >> X0;

    cout << endl;

    // generujemy m + 5 liczb pseudolosowych

    for(i = 1; i <= m + 5; i++)
    {
        X0 = (a * X0 + c) % m;
        cout << X0 << " ";
    }

    cout << endl << endl;

    return 0;
}

Generator liczb pseudolosowych w języku C++

Język C++ posiada wbudowany dobry generator liczb pseudolosowych, do którego dostęp mamy za pomocą dwóch funkcji:

Generator pseudolosowy języka C++ pozwala nam uzyskiwać wartości pseudolosowe w zakresie od 0 do 32767. Poniższy program generuje 20 pierwszych liczb pseudolosowych:

// Liczby pseudolosowe w C++
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

int main()
{
    for(int i = 1; i <= 20; i++) cout << setw(5) << rand() << endl;

    return 0;
}

Zwróć uwagę, iż przy każdym uruchomieniu programu są to te same liczby:

   41
18467
 6334
26500
19169
15724
11478
29358
26962
24464

Spowodowane jest to tym, iż ziarno generatora zawsze startuje od takiej samej wartości. Aby to zmienić, musimy je na początku programu zainicjować wartością, która będzie przy każdym uruchomieniu inna. Tutaj wykorzystujemy funkcję time(), która zwraca wartość bieżącego czasu. Istotne dla nas jest jedynie to, iż wartość ta różni się przy każdym uruchomieniu programu, gdyż czas nieubłaganie płynie do przodu. Wynik funkcji time() jest ziarnem generatora i przekazujemy go jako parametr do funkcji srand(), która ustawi to ziarno.

// Liczby pseudolosowe w C++
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
    srand(time(NULL));

    for(int i = 1; i <= 20; i++) cout << setw(5) << rand() << endl;

    return 0;
}

Teraz każde uruchomienie daje inny ciąg liczb pseudolosowych. Generator pseudolosowy należy inicjować nowym ziarnem tylko raz, na samym początku programu.

Generacja liczb pseudolosowych o zadanym zakresie

Funkcja rand() zwraca nam liczby pseudolosowe o zakresie od 0 do 32767. Jeśli chcemy mieć mniejszy zakres tych liczb, np. od 0 do m  - 1, m  < 32768, to wynik funkcji rand() poddajemy operacji modulo m:

rand() % m  - daje liczby pseudolosowe w zakresie od 0 do m  - 1.

// Liczby pseudolosowe w C++
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
    int m;

    cout << "m = "; cin >> m;

    cout << endl;

    srand(time(NULL));

    for(int i = 1; i <= 20; i++) cout << setw(5) << rand() % m << endl;

    return 0;
}

Jeśli liczby pseudolosowe mają być generowane w zakresie od a  do b, to stosujemy wzór:

a + rand() % (b - a + 1) - daje liczby pseudolosowe w zakresie od a  do b  włącznie.

// Liczby pseudolosowe w C++
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
    int a,b;

    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;

    cout << endl;

    srand(time(NULL));

    for(int i = 1; i <= 20; i++) cout << setw(5) << a + rand() % (b - a + 1) << endl;

    return 0;
}

---

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

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

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