Matura - programowanie w C++

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 kostką, 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 dźwiękowych, 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.

Obecnie możemy skorzystać z serwisów internetowych, które udostępniają nam liczby losowe z wybranego zakresu, na przykład witryna:

https://www.random.org/

W witrynie dostępny jest interfejs generatora liczb losowych:

W okienku ustawiamy pożądany zakres liczb losowych, po czym klikamy w przycisk Generate. Wylosowana liczba losowa jest wyświetlana w polu Result. Tego typu rozwiązanie pozwala nam losować pojedyncze liczby.

Z drugiej strony liczby losowe używane są powszechnie przy programowaniu komputerów – wszelkiego rodzaju 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 zapamiętania:

• Liczba losowa.
• Dlaczego liczby losowej nie można normalnie uzyskać na komputerze?
• Liczba pseudolosowa: czym różni się od losowej?

Xn  = (a × Xn - 1 + c ) mod m

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ć:

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:

Xn  = (a · Xn - 1 + c ) mod m

Xn  = a · Xn - 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 multiplikatywny 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  = 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(m,a,c) = 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:

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

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,  X0)
m  = 34359738368 = 235
a  = [π  × 109] 
c  = [e  × 109], e  – podstawa logarytmów naturalnych, e  = 2, 7182818284590452353602874713527...

// Generator liczb pseudolosowych
//-------------------------------

#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;
}

m  = 12
a  = 13
c  = 7
X0 = 1

8 3 10 5 0 7 2 9 4 11 6 1 8 3 10 5 0

Jeśli współczynniki generatora LCG są dobrane poprawnie, to generator wygeneruje każdą liczbę z przedziału od 0 do m - 1.Funkcja takiego generatora nazywana jest często funkcją mieszającą (ang. hash function), ponieważ wygenerowane liczby są pomieszane. Napiszemy teraz program, który sprawdzi, ilość liczb wygenerowanych przez generator oraz czy ta ilość jest równa modułowi. Jeśli tak, to generator jest poprawny. Jeśli nie, to współczynniki generatora są dobrane źle. Przeanalizuj dokładnie sposób pracy tego programu.

// Generator liczb pseudolosowych
//-------------------------------

#include <iostream>

using namespace std;

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

    cout << "Test generatora LCG" << endl << endl;
    cout << "m = "; cin >> m;
    cout << "a = "; cin >> a;
    cout << "c = "; cin >> c;

    cout << endl;

    // tworzymy tablicę dynamiczną o rozmiarze m

    bool *T = new bool[m];

    // tablicę wypełniamy wartościami false

    for(i = 0; i < m; i++) T[i] = false;

    // generujemy m liczb pseudolosowych
    // i na ich pozycjach w T umieszczamy true

    x = 0; // ziarno

    for(i = 0; i < m; i++)
    {
        x = (a * x + c) % m;
        T[x] = true;
    }

    // zliczamy wygenerowane liczby

    x = 0; // licznik

    for(i = 0; i < m; i++)
        if(T[i]) x++;

    // sprawdzamy ilość liczb

    cout << "Generator LCG ";

    if(x != m) cout << "nie ";

    cout << "jest poprawny." << endl << endl;

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

Test generatora LCG

m = 12
a = 13
c = 7

Generator LCG jest poprawny.

Test generatora LCG

m = 13
a = 12
c = 7

Generator LCG nie jest poprawny.

Do zapamiętania:

• Generatory LCG addytywne i multiplikatywne i czym się różnią.
• Cechy generatora LCG.
• Metoda wyznaczania współczynników generatora LCG.

Inicjalizacja

Podstawowy generator pseudolosowy w C++ 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ę (interpretacja wyniku funkcji time( ) nas tutaj nie interesuje, ważne jest tylko to, iż wynik zmienia się co sekundę; parametrem funkcji time( ) jest wskaźnik struktury czasu, którą ta funkcja wypełnia informacją o bieżącym czasie, jeśli podamy wartość NULL, czyli wskaźnik zerowy nic nie wskazujący, to funkcja nic nie wypełni i zwróci jedynie informację o czasie jako swój wynik). Funkcja time( ) wymaga dołączenia pliku nagłówkowego ctime. Na początku programu umieszczamy następujące wywołanie:

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

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 = 2¹⁵ - 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ę.

Poniższy program inicjuje generator pseudolosowy i tworzy 10 liczb pseudolosowych:

// Wbudowany generator liczb pseudolosowych
//-----------------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    unsigned i;

    srand(time(NULL)); // Inicjalizacja

    for(i=0; i < 10; i++)
        cout << rand() << endl;

    return 0;
}

Zmień inicjalizację kolejno na srand(1), srand(2), srand(3) i uruchom program kilkakrotnie. Wyciągnij wnioski.

Generacja liczb pseudolosowych z zadanego przedziału

Standardowo funkcja rand( ) zwraca liczbę pseudolosową całkowitą od 0 do 32767. Jeśli chcemy mieć liczby z przedziału od 0 do A , gdzie A < 32767, to wykorzystujemy operację modulo:

rand( ) % (A + 1)

Poniższy program generuje 10 liczb z przedziału od 0 do 5:

// Wbudowany generator liczb pseudolosowych
//-----------------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    unsigned i;

    srand(time(NULL));

    for(i=0; i < 10; i++)
        cout << rand() % 6 << " ";
    cout << endl << endl;

    return 0;
}

Jeśli liczby mają zakres od A do B, to stosujemy wzór:

A + rand( ) % (B - A + 1)

Poniższy program wyświetla wynik 10 rzutów kostką:

// Wbudowany generator liczb pseudolosowych
//-----------------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    unsigned i;

    srand(time(NULL));

    for(i=0; i < 10; i++)
        cout << 1 + rand() % 6 << " ";
    cout << endl << endl;

    return 0;
}

Możemy również generować zmiennoprzecinkowe liczby pseudolosowe. Poniższy program tworzy 10 liczb pseudolosowych z przedziału od 0 do 1:

// Wbudowany generator liczb pseudolosowych
//-----------------------------------------

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

using namespace std;

int main()
{
    unsigned i;

    srand(time(NULL));

    cout << fixed << setprecision(8);
    for(i=0; i < 10; i++)
        cout << rand() / (double) RAND_MAX << endl;
    cout << endl << endl;

    return 0;
}

Jeśli chcemy otrzymać liczby z przedziału domkniętego <a,b>, to stosujemy wzór:

a + (rand( ) / (double) RAND_MAX) * (b - a)

Poniższy program generuje 10 liczb pseudolosowych z przedziału od 0,5 do 0,7:

// Wbudowany generator liczb pseudolosowych
//-----------------------------------------

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

using namespace std;

int main()
{
    unsigned i;

    srand(time(NULL));

    cout << fixed << setprecision(8);
    for(i=0; i < 10; i++)
        cout << 0.5 + (rand( ) / (double) RAND_MAX) * 0.2 << endl;
    cout << endl << endl;

    return 0;
}

Podsumowanie:

Inicjalizacja generatora pseudolosowego: srand(time(NULL))

Liczby pseudolosowe z przedziału całkowitego od 0 do 32767: rand( )

Liczby pseudolosowe z przedziału całkowitego od 0 do A: rand( ) % (A + 1)

Liczby pseudolosowe z przedziału całkowitego od A do B: A + rand( ) % (B - A + 1)

Liczby pseudolosowe z przedziału rzeczywistego od 0 do 1: rand( ) / (double) RAND_MAX

Liczby pseudolosowe z przedziału rzeczywistego od 0 do a: rand( ) / (double) RAND_MAX * a

Liczby pseudolosowe z przedziału rzeczywistego od a do b: a + rand( ) / (double) RAND_MAX * (b - a)

Do zastanowienia się

Przedział liczb rzeczywistych może występować w następujących postaciach:

• (a,b) - obustronnie otwarty
• <a,b> - obustronnie domknięty
• <a,b) - lewostronnie domknięty, prawostronnie otwarty
• (a,b> - lewostronnie otwarty, prawostronnie domknięty

Jak zmodyfikować wzory na liczby pseudolosowe, aby otrzymać liczby z przedziałów:

• <0,1)
• (0,1>
• (0,1)
• <a,b)
• (a,b>
• (a,b)

Generator wbudowany generuje 15-bitowe liczby pseudolosowe o zakresie od 0 do 32767. Jak otrzymać 30-bitowe liczby pseudolosowe o zakresie od 0 do 1073741823?