Kody binarne

Naturalny kod binarny pozwala kodować liczby naturalne oraz liczbę zero. Niestety, nie można w nim zapisywać liczb ujemnych. W naszym systemie liczby ujemne zapisujemy z pomocą znaku minus, który stawiamy przed pierwszą cyfrą. Jest to dodatkowy symbol. Jednakże w świecie komputerów istnieją tylko bity, które mogą przyjmować dwie różne wartości: 0 lub 1. Nie możemy zatem po prostu zapisać liczby -5 jako -101, ponieważ wymagałoby to nowej wartości dla bitów. Musimy zastosować pewną umowę, która pozwoli reprezentować liczby ujemne wyłącznie za pomocą bitów, czyli zer i jedynek. W ten sposób powstanie nowy kod binarny.

Umówmy się, że najstarszy bit liczby będzie tzw. bitem znaku, tzn. nie będzie miał przydzielonej wagi jak inne bity, lecz będzie sygnalizował, czy liczba jest dodatnia "0" lub ujemna "1".

Załóżmy, że mamy kod 8-bitowy b₇b₆b₅b₄b₃b₂b₁b₀. W takim kodzie bity od b₆ do b₀ reprezentują wartość liczby w kodzie NBC, natomiast bit b₇ określa znak tej liczby:

• b₇ = 0, liczba jest dodatnia, +
• b₇ = 1, liczba jest ujemna, -

Dla 8 bitów możemy zapisywać liczby od -127 ( 111111111 ) do  +127 ( 011111111 ). Na przykład -5 zapiszemy jako 10000101.

Otrzymaliśmy kod, który nazywamy kodem znak-moduł. Chociaż jest to kod prosty w budowie i łatwy do zrozumienia, to jednak nie jest powszechnie stosowany. Dlaczego? Powodem jest to, iż wykonywanie operacji arytmetycznych wymaga analizowania znaków liczb. Na przykład przy dodawaniu liczby dodatniej i ujemnej, musimy wykonać faktycznie odejmowanie, gdyż inaczej wynik będzie zły. Komplikuje to układy arytmetyczne komputerów, a zatem zwiększa ich koszt. Wymyślono zatem inny sposób reprezentacji liczb całkowitych, który nie wymaga zmian w układach arytmetycznych, należy jedynie inaczej interpretować wyniki. Kod realizujący ten wymóg nazywa się kodem uzupełnień do dwóch, U2.

Tutaj, podobnie jak w kodzie znak-moduł, najstarszy bit posiada inne znaczenie od pozostałych bitów liczby. Jest to bit znaku, lecz tym razem ma on swoją wagę, która jest ujemną potęgą 2 o wykładniku będącym numerem pozycji bitu. W efekcie wagi pozycji liczby U2 są takie same jak w kodzie NBC, tylko waga najstarszego bitu jest ujemna. Zobaczmy jak to działa na liczbach 4-bitowych:

Jeśli najstarszy bit jest równy 0, to mamy zwykłą liczbę NBC, np.:

Jest to liczba dodatnia.

Jeśli najstarszy bit jest równy 1, to w wartości liczby pojawia się waga ujemna. Zwróć uwagę, że waga ta na moduł jest zawsze o 1 większa od sumy pozostałych wag. Z tego powodu przeważa ona wartość liczby w stronę liczb ujemnych:

Wartość liczby jest sumą wag pozycji, na których stoją bity 1. Czyli dokładnie tak samo jak w kodzie NBC.  Stąd najmniejszą liczbą jest taka, w której 1 stoi na pozycji znaku ( wartość ujemna ), a wszystkie pozostałe bity mają wartość 0:

Dla n-bitowej liczby jest to -2^{n - 1}.

Największą wartość otrzymamy dla liczby, w której bit znaku ma wartość 0 ( brak wagi ujemnej ), a wszystkie pozostałe bity mają stan 1 ( suma wszystkich wag dodatnich ):

Dla n-bitowej liczby jest to 2^{n - 1} - 1.

Otrzymujemy zatem zakres n-bitowych liczb U2 od -2^{n - 1} do 2^{n - 1} - 1.

Liczby U2 można dodawać dokładnie tak samo jak liczby NBC, lecz wynik należy interpretować w kodzie U2. Dla przykładu wykonamy proste dodawanie dwóch liczb U2 4-bitowych:

Dodajemy liczby NBC:

Wynik jest 5-bitowy. Ograniczamy go do 4 bitów:

Otrzymaliśmy wynik 4, który jest wynikiem dodawania 7 + (-3) = 4. Jak widzisz, wynik jest poprawny, pomimo wykonania działania na zwykłych liczbach naturalnych NBC. Zatem liczby U2 pozwalają reprezentować liczby całkowite dodatnie i ujemne. Dodatkowo operacje arytmetyczne na liczbach U2 można wykonywać dokładnie tak samo jak na liczbach NBC, wynik musi być interpretowany jako liczba U2. Więcej na ten temat znajdziesz w tym artykule.

Kod U2 jest standardowo używany do reprezentacji liczb całkowitych w komputerach. W języku C++ mamy do dyspozycji następujące typy danych:

Zwykle nie będziesz musiał przeliczać wartości dziesiętnych na binarne, ponieważ zawsze robi to za ciebie komputer i chwała mu za to. Lecz musisz pamiętać o własnościach liczb binarnych, np. o dopuszczalnych zakresach oraz o rozmiarze danych w pamięci.

Poniższy program wypisuje rozmiary typów danych całkowitych dla twojego kompilatora:

// Sprawdzenie typów danych U2
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    signed char cnv,cpv;
    short int snv,spv;
    int inv,ipv;
    long long int lnv,lpv;

    setlocale(LC_ALL,"");

    // Wartości minimalne i maksymalne
    cpv = spv = ipv = lpv = 0xffffffffffffffffL;
    cpv = (unsigned char) cpv >> 1;
    spv = (unsigned short int) spv >> 1;
    ipv = (unsigned int) ipv >> 1;
    lpv = (unsigned long long int) lpv >> 1;
    cnv = ~cpv;
    snv = ~spv;
    inv = ~ipv;
    lnv = ~lpv;

    // Wyniki

     cout << "Liczby całkowite w typach danych języka C++" << endl
          << "-------------------------------------------" << endl << endl;
     cout << "Nazwa typu    Bajty Bity Zakres" << endl;
     cout << left << setw(13) << "signed char" << right
          << setw(5)  << sizeof(signed char)
          << setw(5)  << sizeof(signed char) * 8 << " "
          << (int)cnv << " ... " << (int)cpv << endl;
     cout << left << setw(13) << "short int" << right
          << setw(5)  << sizeof(short int)
          << setw(5)  << sizeof(short int) * 8 << " "
          << snv << " ... " << spv << endl;
     cout << left << setw(13) << "int" << right
          << setw(5)  << sizeof(int)
          << setw(5)  << sizeof(int) * 8 << " "
          << inv << " ... " << ipv << endl;
     cout << left << setw(13) << "long long int" << right
          << setw(5)  << sizeof(long long int)
          << setw(5)  << sizeof(long long int) * 8 << " "
          << lnv << " ... " << lpv << endl;
    return 0;
}

Jak zamienić liczbę dziesiętną na liczbę U2? Jeśli koniecznie musisz coś takiego zrobić, to najprostszym rozwiązaniem jest poniższy program. Zamienia on liczby dziesiętne dodatnie i ujemne na ich odpowiedniki w kodzie U2. Liczba bitów powinna wynosić od 1 do 64.

// Konwersja na kod U2
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//------------------------------

#include <iostream>

using namespace std;

int main()
{
    int nb;
    long long int n;
    unsigned long long int m;

    setlocale(LC_ALL,"");

    cout << "Konwersja liczby dziesiętnej na kod U2" << endl
         << "--------------------------------------" << endl << endl;

    cout << "Liczba bitów U2  : "; cin >> nb;

    if((nb < 1) || (nb > 64)) cout << "Zła liczba bitów !!!";
    else
    {
        cout << "Liczba dziesiętna: "; cin >> n;
        cout << "Liczba U2        : ";

        // ustawiamy maskę

        m = 1L << (nb - 1);

        // Wyświetlamy kolejne bity liczby U2

        while(m)
        {
            cout << ((m & n) > 0);
            m >>= 1;
        }
    }
    cout << endl << endl;

    return 0;
}

Jeśli nie masz możliwości użyć tego programu, to konwersji można dokonać na kilka sposobów. Ponieważ zakładam, iż umiesz już konwertować liczby dziesiętne na kod NBC (opis w poprzednim rozdziale ), wykorzystajmy tę umiejętność dla kodu U2.

Kody U2 mają określoną liczbę bitów, ponieważ najstarszy bit jest zawsze bitem znakowym i posiada wagę ujemną. Załóżmy, że chcesz zapisać w 8-bitowym kodzie U2 liczbę 55. Najpierw konwertujesz 55 na kod NBC:

Liczba NBC ma tylko 6 bitów. Uzupełniasz zatem bity do 8 przez dodanie dwóch bitów 0 na początku zapisu liczby:

Gotowe.

Załóżmy teraz, że chcesz przekonwertować liczbę -44 na 8-bitowy kod U2. Tym razem masz liczbę ujemną. W kodzie 8-bitowym U2 bit znakowy ma wagę (-2⁷) = -128. Ile należy dodać do -128, aby otrzymać -44?

84 jest wartością pozostałych bitów liczby U2. Zamieniamy 84 na kod NBC:

Otrzymana liczba NBC ma 7 bitów, dodajesz zatem bit znakowy 1 ( ponieważ liczba ma być ujemna ) i otrzymujesz wynik:

Kod U2 pozwala kodować liczby całkowite dodatnie, ujemne oraz zero. Jest on zatem bardziej uniwersalny od kodu NBC. Nie oznacza to jednak, iż wypiera go całkowicie z obliczeń komputerowych. Zauważ, że liczby U2 mają o połowę mniejszy zakres wartości dodatnich ( konsekwencja bitu znakowego ) od liczb NBC o tej samej liczbie bitów:

Czasem musimy operować na dużych liczbach dodatnich. W takim przypadku kod NBC da nam ich większy zakres.

Operacja dodawania liczb U2 daje poprawne wyniki pod warunkiem, że wyniki te mieszczą się w zakresie liczb U2. W przeciwnym razie mamy nadmiar lub niedomiar i wynik jest błędny. Kiedy przy dodawaniu możemy otrzymać nadmiar lud niedomiar? Otóż wtedy, gdy wynik dodawania na moduł rośnie. A dzieje się tak tylko wtedy, gdy obie dodawane liczby posiadają ten sam znak. Jeśli znak wyniku jest taki sam jak znak dodawanych liczb, to wynik jest poprawny. Jeśli znak wyniku jest różny od znaku dodawanych liczb, to mamy nadmiar/niedomiar. Na przykład 8-bitowe liczby U2 posiadają poprawny zakres wartości od -128 do 127. Komputer dodaje te liczby tak, jakby były liczbami NBC, a wynik interpretuje w kodzie U2. Po to właśnie przyjęto kod U2, aby nie zmieniać zasad wykonywania operacji arytmetycznych. Sprawdźmy:

Odrzucamy 9-ty bit wyniku i otrzymujemy:

Wynik jest poprawny.

Teraz wykonajmy podobne działanie na dwóch liczbach dodatnich:

W kodzie U2 wynik ma inny znak niż znak obu dodawanych liczb, wystąpił zatem nadmiar/niedomiar i wynik jest nieprawidłowy.

Podsumujmy:

Poniższy program dodaje dwie 8-bitowe liczby U2 i sprawdza poprawność wyniku.

// Dodawanie liczb U2
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//------------------------------

#include <iostream>

using namespace std;

int main()
{
    int x;
    signed char a,b,r; // Zmienne 8-bitowe U2

    setlocale(LC_ALL,"");

    cout << "Dodawanie dwóch 8-bitowych liczb U2" << endl
         << "-----------------------------------" << endl << endl;

    cout << "Wprowadź dwie liczby z zakresu od -128 do 127" << endl << endl;

    // dane wczytujemy jako liczby 32-bitowe i przepisujemy je do
    // zmiennych 8-bitowych U2

    cout << "Liczba nr 1: "; cin >> x; a = x;
    cout << "Liczba nr 2: "; cin >> x; b = x;
    cout << endl;

    // Wykonujemy dodawanie i wyświetlamy wynik

    r = a + b;

    cout << (int)a << " + " << (int)b << " = " << (int)r;

    // Sprawdzamy poprawność wyniku
    // Jeśli obie liczby a i b mają te same znaki,
    // to poniższe wyrażenie jest prawdziwe

    if((a ^ b ^ 0x80) & 0x80)
    {
        // Jeśli wynik ma inny znak od znaku liczby a,
        // to poniższe wyrażenie jest prawdziwe
        // i oznacza błędny wynik dodawania

        if((a ^ r) & 0x80) cout << " Błąd - wynik poza zakresem !!!";
    }

    cout << endl << endl;

    return 0;
}

Odejmowanie jest po prostu dodawaniem liczby przeciwnej, zatem po uwzględnieniu tego faktu reszta reguł jest identyczna jak dla dodawania:

Przy mnożeniu liczb U2 poprawność wyniku można sprawdzić tą samą metodą, którą podaliśmy dla liczb NBC:

Poniższy program mnoży dwie 64-bitowe liczby NBC i sprawdza poprawność wyniku.

// Mnożenie liczb całkowitych U2
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>

using namespace std;

int main()
{
    long long int a,b,r;

    setlocale(LC_ALL,"");

    cout << "Mnożenie 64-bitowych liczb całkowitych w kodzie U2" << endl
         << "--------------------------------------------------" << endl << endl;
    // Odczytujemy dane wejściowe

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

    // Wykonujemy mnożenie

    r = a * b;

    // Wypisujemy wynik

    cout << a << " * " << b << " = " << r;

    // Sprawdzamy nadmiar

    if (b && (a != r / b)) cout << " Wynik błędny, NADMIAR !!!";
    else                   cout << " Wynik prawidłowy";

    cout << endl << endl;

    return 0;
}

Dzielenie liczb U2 jest zawsze dzieleniem całkowitoliczbowym i obowiązują tutaj te same zasady, co przy liczbach NBC:

Przykładowy program przelicza stopnie Fahrenheita na stopnie Celsjusza i na odwrót. Wczytana liczba jest traktowana jako temperatura w stopniach Celsjusza lub w stopniach Fahrenheita. Wykorzystujemy wzory:

Wyniki będą zaokrąglone do liczb całkowitych.

// Działania na liczbach U2
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>

using namespace std;

int main()
{
    int t,tc,tf;

    setlocale(LC_ALL,"");

    cout << "Przeliczanie pomiędzy stopniami Celsjusza i Fahrenheita" << endl
         << "-------------------------------------------------------" << endl << endl;
    // Odczytujemy Temperaturę

    cout << "Temperatura = "; cin >> t;
    cout << endl;

    // Przeliczamy

    tc = (5 * (t - 32)) / 9;
    tf = (9 * t) / 5 + 32;

    // Wypisujemy wyniki

    cout << t << "°C = " << tf << "°F" << endl << endl
         << t << "°F = " << tc << "°C" << endl << endl;


    return 0;
}

Liczba losowa ( ang. random number ) jest liczbą otrzymaną w wyniku pewnego procesu losowego, np. losowania, rzutu monetą, kostką, rozdania potasowanych kart itp. Cechą podstawową liczby losowej jest to, iż jej konkretnej wartości nie możemy w żaden sposób określić przed losowaniem, możemy jedynie określić jej zakres, np. podczas rzutu kostką wiemy, że wynikiem może być od 1 do 6 oczek, pomijając przypadki, gdy kość się rozpadnie lub zatrzyma na krawędzi, czego również nie da się wcześniej przewidzieć. Wartości liczb losowych pojawiają się z pewnym prawdopodobieństwem, które im jest wyższe, tym częściej dana liczba pojawia się w wynikach. Rachunkiem prawdopodobieństwa nie będziemy się tutaj zajmować, jednak liczby losowe są czasem stosowane w obliczeniach, zatem warto coś o nich wiedzieć.

Prawdziwa liczba losowa jest trudna do otrzymania na komputerze bez dodatkowego wyposażenia. Wymaga ona procesu, którego wyniku nie da się określić, a wszystkie operacje wykonywane przez komputer są ściśle określone. Starano się to rozwiązać za pomocą różnych dodatkowych urządzeń, np. generatorów szumu, które wykorzystują procesy kwantowe zachodzące w półprzewodnikach, jednakże takie urządzenia nie są standardowym wyposażeniem i nie każdy użytkownik ma do nich dostęp. Dlatego często zadowalamy się namiastką liczb losowych – liczbami pseudolosowymi ( ang. pseudorandom numbers ). Słowo "pseudo" pochodzi z języka łacińskiego i oznacza "jakby", czyli liczby pseudolosowe to jakby liczby losowe. Przypominają one liczby losowe, mogą posiadać ich niektóre własności, np. częstość występowania, lecz są otrzymywane na drodze algorytmicznej. Oznacza to, iż znając sposób ich tworzenia oraz jedną z nich, możemy wyliczyć wszystkie następne, zatem nie ma tutaj żadnej losowości. Pomimo tej wady ( a może zalety ), liczby pseudolosowe mają ogromne zastosowanie w informatyce, począwszy od gier a skończywszy na szyfrowaniu i symulacjach.

Liczby pseudolosowe tworzy się za pomocą funkcji zwanych generatorami liczb pseudolosowych. Generatorów pseudolosowych wymyślono mnóstwo. Aby zrozumieć ich działanie, przeanalizujmy prostą funkcję o postaci:

Gdzie:

W funkcji występuje działanie modulo, czyli reszta z dzielenia dwóch liczb całkowitych. W języku C++ realizuje je operator arytmetyczny %:

Następna liczba pseudolosowa X_{n + 1} powstaje z liczby poprzedniej X_n. Oznacza to, iż liczby te nie są dowolne, lecz tworzą ciąg:

Ciąg ten również nie jest nieskończony, ponieważ w funkcji występuje reszta z dzielenia przez m. Reszty z dzielenia mogą przyjmować wartości tylko w przedziale od 0 do m - 1. Zatem wszystkich możliwych wartości jest co najwyżej m. Co więcej, wartości te powtarzają się po wygenerowaniu m liczb:

Pierwszą liczbę X₀ tego ciągu nie obliczamy, lecz określamy. Nazywa się ona ziarnem pseudolosowym ( ang. pseudorandom seed ) i powinna mieć wartość od 0 do m - 1. Z ziarna powstają wszystkie kolejne liczby ciągu. Po wygenerowaniu m liczb pseudolosowych kolejną liczbą jest z powrotem ziarno pseudolosowe i cały ciąg powtarza się. Liczby pseudolosowe tworzą zamknięty pierścień wartości. Ziarno określa pozycję startową w tym pierścieniu:

Aby funkcja wygenerowała wszystkie liczby w przedziale od 0 do m - 1, należy odpowiednio dobrać jej współczynniki. Procedura jest następująca:

1. Określamy zakres liczb pseudolosowych. Przyjmijmy od 0 do 25.
2. Moduł m powinien być o 1 większy od największej liczby pseudolosowej do wygenerowania. U nas m = 26.
3. Przyrost c musi być względnie pierwszy z modułem m. Oznacza to, iż nie posiadają one wspólnych czynników pierwszych. Rozkładamy moduł na czynniki pierwsze:
   26 = 2 · 13
   Przyrost c nie może w rozkładzie posiadać czynników 2 i 13. Przyjmijmy zatem c = 11.
4. Mnożnik a określa reguła, która mówi, iż (a - 1) musi być podzielne przez każdy czynnik modułu m. Jeśli moduł m dzieli się przez 4, to (a - 1) również powinno dzielić się przez 4. U nas przyjmijmy:
   (a - 1) = 2 · 13
   a = 26 + 1
   a = 27

Podsumujmy:

Funkcja generatora ma wzór:

Jako X₀ możemy przyjąć dowolną liczbę od 0 do 25. Przyjęcie innej wartości nic nie da, ponieważ operacja modulo i tak sprowadzi wynik do zakresu od 0 do 25.

Poniższy program generuje liczby pseudolosowe wg tej funkcji.

// Liczby pseudolosowe
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>

using namespace std;

int main()
{
    // Współczynniki generatora pseudolosowego

    const int a = 27;
    const int c = 11;
    const int m = 26;

    // Liczba pseudolosowa

    int x;

    setlocale(LC_ALL,"");

    cout << "Przykładowy generator liczb pseudolosowych z zakresu od 0 do 25" << endl
         << "---------------------------------------------------------------" << endl << endl;

    // Wczytujemy ziarno pseudolosowe

    cout << "X0 = "; cin >> x;
    cout << endl;

    // Generujemy 26 liczb pseudolosowych

    for(int i = 0; i < 26; i++)
    {
        // Wyznaczamy kolejną liczbę pseudolosową

        x = a * (x + c) % m;

        // Wyświetlamy jej wartość

        cout << x << " ";
    }

    cout << endl << endl;

    return 0;
}

Przyglądnij się dokładnie wynikom otrzymanym w tym programie. Ostatnią liczbą jest zawsze ziarno pseudolosowe, zatem ciąg kolejnych 26 liczb będzie taki sam. Liczby są pomieszane, dlatego funkcja opisana powyżej często nazywa się funkcją mieszającą lub haszującą ( ang. hashing function ). Jeśli poprawnie dobierzemy współczynniki a, c i m, to każda liczba w tym ciągu pojawi się dokładnie jeden raz. Aby liczby wyglądały jak losowe, moduł m powinien być duży, wtedy powtórka liczby ciągu wystąpi dopiero po wygenerowaniu dużej ich ilości.

Funkcji pseudolosowej nie musimy sami tworzyć, o ile nie jest to konieczne. W języku C++ dostępny jest generator liczb pseudolosowych, z którego zawsze możesz skorzystać.

Poniższy program generuje 10 liczb pseudolosowych za pomocą wbudowanego generatora pseudolosowego.

// Liczby pseudolosowe
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

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

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    cout << "Wbudowany generator liczb pseudolosowych" << endl
         << "----------------------------------------" << endl << endl;

    // Generujemy 10 liczb pseudolosowych

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

    cout << endl << endl;

    return 0;
}

Uruchom program kilka razy i porównaj otrzymane wyniki. Za każdym razem otrzymujesz ten sam ciąg wartości. Dzieje się tak dlatego, iż ziarno pseudolosowe jest zawsze inicjowane na tę samą wartość przy uruchomieniu programu. Skoro tak, to generowany ciąg pseudolosowy staruje zawsze od tej samej liczby początkowej. Aby otrzymywać inne ciągi liczb pseudolosowych, musisz zmieniać wartość ziarna pseudolosowego.

Poniższy program pozwala ci określić ziarno pseudolosowe.

// Liczby pseudolosowe
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

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

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    int x;

    cout << "Ziarno wbudowanego generatora liczb pseudolosowych" << endl
         << "--------------------------------------------------" << endl << endl;

    // Odczytujemy wartość ziarna pseudolosowego

    cout << "Podaj ziarno pseudolosowe od 0 do " << RAND_MAX << endl << endl
         << "X0 = "; cin >> x;
    cout << endl;

    // Ustawiamy nowe ziarno pseudolosowe

    srand(x);

    // Generujemy 10 liczb pseudolosowych na podstawie nowego ziarna

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

    cout << endl << endl;

    return 0;
}

Aby przy każdym uruchomieniu programu otrzymywać różne ciągi pseudolosowe, powinniśmy zapewnić różne wartości ziarna pseudolosowego. W praktyce jako ziarno pseudolosowe używamy wartości czasu odczytanej z wewnętrznego zegara, w który wyposażony jest każdy współczesny komputer osobisty. Wartość ta zmienia się co sekundę, zatem przy każdym uruchomieniu programu będzie inna.

Poniższy program pokazuje, jak można to zrobić

// Liczby pseudolosowe
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

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

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    cout << "Uprzypadkowienie wbudowanego generatora liczb pseudolosowych" << endl
         << "------------------------------------------------------------" << endl << endl;

    // Ustawiamy nowe ziarno pseudolosowe z zegara

    srand(time(NULL));

    // Generujemy 10 liczb pseudolosowych na podstawie nowego ziarna

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

    cout << endl << endl;

    return 0;
}

Wbudowany generator języka C++ generuje liczby pseudolosowe w zakresie od 0 do 32767 ( stała RAND_MAX ). Zakres ten określa 15-bitowe liczby NBC. Wewnętrznie liczby pseudolosowe są tworzone na 32 bitach, a funkcja rand() zwraca 15 najmłodszych bitów wygenerowanej liczby pseudolosowej. Ma to na celu zwiększenie ich przypadkowości. 32 bity daje nam okres ponad 4 miliardów liczb, czyli ciąg ten zaczyna się powtarzać po wygenerowaniu 4 miliardów liczb pseudolosowych.

Jak zwiększyć zakres generowanych liczb pseudolosowych do 30 bitów? Rozwiązanie jest proste: należy wywołać funkcję rand() dwukrotnie z odpowiednio przesuniętymi bitami w lewo i połączyć wyniki operatorem bitowej alternatywy:

rand() | (rand() << 15)

Zwiększy to zakres generowanych liczb do 1073741823 (2³⁰ - 1 ). Lepsze rozwiązanie pokażemy dalej.

Funkcja rand() nadaje się do generowania niezbyt dużych liczb pseudolosowych. Aby otrzymać liczby z innego zakresu niż 0...32767 stosujemy prosty wzór:

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

Wynikiem są liczby pseudolosowe z zakresu od A do B.

Poniższy program wyświetla wyniki rzutów kostką w postaci tabeli 6 x 6:

// Liczby pseudolosowe
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

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

using namespace std;

int main()
{

    setlocale(LC_ALL,"");

    cout << "Rzuty kostką" << endl
         << "------------" << endl << endl;

    // Ustawiamy nowe ziarno pseudolosowe z zegara

    srand(time(NULL));

    // Generujemy 6 serii rzutów kostką

    for(int j = 0; j < 6; j++)
    {
        cout << " ";
        for(int i = 0; i < 6; i++) cout << 1 + rand() % 6 << " ";
        cout << endl;
    }

    cout << endl;

    return 0;
}

W języku C++ od wersji 11 istnieje cała biblioteka obiektów związanych z generacją liczb pseudolosowych. Dostęp do jej funkcji uzyskuje się po dołączeniu do programu pliku nagłówkowego <random>.

Standardowy generator liczb pseudolosowych języka C++ posiada wiele ograniczeń, z których najbardziej bolesnym jest mały zakres generowanych liczb ( 0 ... RAND_MAX, RAND_MAX = 32767). Oczywiście ograniczenie to można ominąć losując kilka liczb pseudolosowych i łącząc je w jedną liczbę. Jest to jednak niewygodne. W takich wypadkach pomocna może być biblioteka obiektowa random. Udostępnia ona różne generatory liczb pseudolosowych oraz różne rozkłady liczbowe. Tutaj krótko opiszemy podstawowe zasady pracy z obiektami pseudolosowymi.

Generator pseudolosowy jest klasą C++. Istnieją typy ogólne tych klas oraz typy zaadaptowane do określonych rodzajów generatorów pseudolosowych:

Każda klasa generatora posiada funkcje składowe:

Zobaczmy, jak to działa w praktyce. Najpierw musisz włączyć obsługę standardu 11 języka C++ w swoim kompilatorze. Jeśli korzystasz ze środowiska Code::Blocks, to z menu wybierz opcję Settings→Compiler i w okienku dialogowym zaznacz wskazaną opcję kompilatora:

Poniższy program tworzy różne generatory liczb pseudolosowych i wyświetla informacje o zakresach tworzonych przez nie liczb.

// Liczby pseudolosowe
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>
#include <ctime>
#include <random>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    cout << "Zakresy bibliotecznych generatorów pseudolosowych" << endl
         << "-------------------------------------------------" << endl << endl;

    // Tworzymy klasy generatorów pseudolosowych

    default_random_engine dgen(time(NULL));
    minstd_rand mgen(time(NULL));
    minstd_rand0 m0gen(time(NULL));
    mt19937 mtgen(time(NULL));
    mt19937_64 mt64gen(time(NULL));
    ranlux24_base rl24gen(time(NULL));
    ranlux48_base rl48gen(time(NULL));
    knuth_b kbgen(time(NULL));

    // Wyświetlamy zakresy liczb pseudolosowych dla każdego generatora

    cout << "standardowy          : " << dgen.min() << " ... " << dgen.max() << endl;
    cout << "multiplikatywny LCG  : " << mgen.min() << " ... " << mgen.max() << endl;
    cout << "multiplikatywny LCG 0: " << m0gen.min() << " ... " << m0gen.max() << endl;
    cout << "Mersenne Twister     : " << mtgen.min() << " ... " << mtgen.max() << endl;
    cout << "Mersenne Twister 64  : " << mt64gen.min() << " ... " << mt64gen.max() << endl;
    cout << "Ranlux 24-bitowy     : " << rl24gen.min() << " ... " << rl24gen.max() << endl;
    cout << "Ranlux 48-bitowy     : " << rl48gen.min() << " ... " << rl48gen.max() << endl;
    cout << endl;

    return 0;
}

Następny program generuje 15 liczb pseudolosowych za pomocą wybranego generatora pseudolosowego. Generator możesz zmienić na inny.

// Liczby pseudolosowe
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>
#include <ctime>
#include <random>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    cout << "Generacja liczb pseudolosowych generatorem Mersenne Twister" << endl
         << "----------------------------------------------------------" << endl << endl;

    // Tworzymy generator pseudolosowy Mersenne Twister

    mt19937_64 mt64gen(time(NULL));

    // Wyświetlamy 15 liczb pseudolosowych

    for(int i = 0; i < 15; i++) cout << setw(22) << mt64gen() << endl;

    cout << endl;

    return 0;
}

Jeśli chcesz otrzymywać liczby z zakresu A...B, to możesz zastosować podany wcześniej wzór:

Istnieje jednak lepszy sposób, który wykorzystuje rozkład. Rozkład określa prawdopodobieństwo pojawienia się określonej wartości w zakresie generowanych liczb. Jeśli prawdopodobieństwo każdej wartości w zakresie jest takie samo, to mamy do czynienia z rozkładem jednorodnym ( ang. uniform distribution ). Rozkład nazywamy dyskretnym, jeśli w podanym zakresie liczby mogą przyjmować tylko wybrane wartości ( np. całkowite ).

Biblioteka random udostępnia mnóstwo różnych rozkładów, których dokładne omówienie wykracza poza ramy tego artykułu.

Rozkład w bibliotece random jest klasą. Zasady użycia są następujące:

1. Tworzymy klasę rozkładu przekazując do jej konstruktora odpowiednie parametry. Dla rozkładu jednorodnego są to granice zakresu liczb pseudolosowych.
2. Tworzymy klasę generatora liczb pseudolosowych.
3. Generujemy liczby pseudolosowe poprzez operator () klasy rozkładu przekazując w parametrze klasę generatora pseudolosowego.

Poniższy program generuje 200 liczb pseudolosowych o rozkładzie jednorodnym.

// Liczby pseudolosowe
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>
#include <ctime>
#include <random>
#include <iomanip>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    cout << "200 liczb pseudolosowych od 1 do 999 o rozkładzie jednorodnym" << endl
         << "-------------------------------------------------------------" << endl << endl;

    // Tworzymy klasę szablonową int rozkładu jednorodnego

    uniform_int_distribution<int> dist(1,999);

    // Tworzymy standardowy generator pseudolosowy

    default_random_engine gen(time(NULL));

    // Wyświetlamy 200 liczb pseudolosowych

    int c = 0;
    for(int i = 0; i < 200; i++)
    {
        cout << setw(4) << dist(gen);
        c++;
        if(c == 10)
        {
            c = 0; cout << endl;
        }
    }

    cout << endl;

    return 0;
}