Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
SPIS TREŚCI |
|
Podrozdziały |
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 b7b6b5b4b3b2b1b0. W takim kodzie bity od b6 do b0 reprezentują wartość liczby w kodzie NBC, natomiast bit b7 określa znak tej liczby:
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:
Waga | -8(-23 ) | 4( 22 ) | 2( 21 ) | 1( 20 ) |
Bit | b3 | b2 | b1 | b0 |
Pozycja | 3 | 2 | 1 | 0 |
Jeśli najstarszy bit jest równy 0, to mamy zwykłą liczbę NBC, np.:
0110(U2) = 4 + 2 = 6 |
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:
1110(U2) + -8 + 4 + 2 = -2 |
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:
1000(U2)
=
-8 = -23 10000(U2) = -16 = -24 100000(U2) = -32 = -25 ... 10000000(U2) = -128 = -27 |
Dla n-bitowej liczby jest to -2n - 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 ):
0111(U2)
= 7 = 23 - 1 01111(U2) = 15 = 24 - 1 011111(U2) = 31 = 25 - 1 ... 01111111(U2) = 127 = 27 - 1 |
Dla n-bitowej liczby jest to 2n - 1 - 1.
Otrzymujemy zatem zakres n-bitowych liczb U2 od -2n - 1 do 2n - 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:
0111(U2)
= 7 0111(NBC) = 7 1101(U2) = -8 + 5 = -3 1101(NBC) = 13 |
Dodajemy liczby NBC:
7 + 13 = 20 = 10100(NBC) |
Wynik jest 5-bitowy. Ograniczamy go do 4 bitów:
0100(NBC) = 4 = 0100(U2) = 4 |
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:
Nazwa typu | Liczba bajtów | Liczba bitów | Zakres |
signed char | 1 | 8 | -128...127 |
short int | 2 | 16 | -32768...32767 |
int | 4 | 32 | -2147483648...2147483647 |
long long int | 8 | 64 | -9223372036854775808...9223372036854775807 |
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:
Przykładowy program w języku C++
// 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; } |
Wynik |
Liczby całkowite w typach danych języka C++ ------------------------------------------- Nazwa typu Bajty Bity Zakres signed char 1 8 -128 ... 127 short int 2 16 -32768 ... 32767 int 4 32 -2147483648 ... 2147483647 long long int 8 64 -9223372036854775808 ... 9223372036854775807 |
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.
Przykładowy program w języku C++
// 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; } |
Wyniki |
Konwersja liczby dziesiętnej na kod U2 -------------------------------------- Liczba bitów U2 : 4 Liczba dziesiętna: -5 Liczba U2 : 1011 |
Konwersja liczby dziesiętnej na kod U2 -------------------------------------- Liczba bitów U2 : 8 Liczba dziesiętna: -25 Liczba U2 : 11100111 |
Konwersja liczby dziesiętnej na kod U2 -------------------------------------- Liczba bitów U2 : 12 Liczba dziesiętna: -1000 Liczba U2 : 110000011000 |
Konwersja liczby dziesiętnej na kod U2 -------------------------------------- Liczba bitów U2 : 125 Zła liczba bitów !!! |
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:
55 = 32 + 16 + 4 + 2 + 1 = 110111(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:
55 = 00110111(U2) |
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ę (-27) = -128. Ile należy dodać do -128, aby otrzymać -44?
-128 + x = -44 x = 128 - 44 x = 84 |
84 jest wartością pozostałych bitów liczby U2. Zamieniamy 84 na kod NBC:
84 = 64 + 16 + 4 = 1010100(NBC) |
Otrzymana liczba NBC ma 7 bitów, dodajesz zatem bit znakowy 1 ( ponieważ liczba ma być ujemna ) i otrzymujesz wynik:
-44 = 11010100(U2) |
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:
Liczba bitów |
Zakres NBC |
Zakres U2 |
4 | 0...15 | -8...7 |
8 | 0...255 | -128...127 |
16 | 0...65535 | -32768...32767 |
32 | 0 ... 4294967295 | -2147483648...2147483647 |
64 | 0 ... 18446744073709551615 | -9223372036854775808...9223372036854775807 |
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:
115 = 01110011(U2/NBC) -25 = 11100111 (U2) = 231 jako NBC (115 - 25)(U2) = (115 + 231)(NBC) = 346(NBC) = 101011010(NBC) |
Odrzucamy 9-ty bit wyniku i otrzymujemy:
01011010(U2) = 90 115 - 25 = 90 |
Wynik jest poprawny.
Teraz wykonajmy podobne działanie na dwóch liczbach dodatnich:
115 = 01110011(U2/NBC) 25 = 00011001(U2/NBC) (115 = 25)(U2) = (115 + 25)(NBC) = 140(NBC) = 10001100(NBC) 10001100(U2) = -128 + 16 + 8 = -104 115 + 25 = -104 |
W kodzie U2 wynik ma inny znak niż znak obu dodawanych liczb, wystąpił zatem nadmiar/niedomiar i wynik jest nieprawidłowy.
Podsumujmy:
Jeśli suma dwóch dodatnich liczb U2 jest ujemna,
to wynik jest nieprawidłowy. Jeśli suma dwóch ujemnych liczb U2 jest dodatnia, to wynik jest nieprawidłowy. W przeciwnym razie wynik jest prawidłowy. |
Poniższy program dodaje dwie 8-bitowe liczby U2 i sprawdza poprawność wyniku.
Przykładowy program w języku C++
// 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; } |
Wyniki |
Dodawanie dwóch 8-bitowych liczb U2 ----------------------------------- Wprowadź dwie liczby z zakresu od -128 do 127 Liczba nr 1: 115 Liczba nr 2: -25 115 + -25 = 90 |
Dodawanie dwóch 8-bitowych liczb U2 ----------------------------------- Wprowadź dwie liczby z zakresu od -128 do 127 Liczba nr 1: -115 Liczba nr 2: 100 -115 + 100 = -15 |
Dodawanie dwóch 8-bitowych liczb U2 ----------------------------------- Wprowadź dwie liczby z zakresu od -128 do 127 Liczba nr 1: 100 Liczba nr 2: 40 100 + 40 = -116 Błąd - wynik poza zakresem !!! |
Dodawanie dwóch 8-bitowych liczb U2 ----------------------------------- Wprowadź dwie liczby z zakresu od -128 do 127 Liczba nr 1: -75 Liczba nr 2: -84 -75 + -84 = 97 Błąd - wynik poza zakresem !!! |
Odejmowanie jest po prostu dodawaniem liczby przeciwnej, zatem po uwzględnieniu tego faktu reszta reguł jest identyczna jak dla dodawania:
Jeśli odjemnik ma inny znak od odjemnej, a wynik
ma ten sam znak co odjemnik, to wynik jest błędny. W przeciwnym razie wynik jest poprawny. |
Przy mnożeniu liczb U2 poprawność wyniku można sprawdzić tą samą metodą, którą podaliśmy dla liczb NBC:
Jeśli (b ≠ 0) i (r = a · b), to (a = r :
b) Jeśli (b = 0), to (r = 0) i wynik jest zawsze poprawny |
Poniższy program mnoży dwie 64-bitowe liczby NBC i sprawdza poprawność wyniku.
Przykładowy program w języku C++
// 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; } |
Wyniki |
Mnożenie 64-bitowych liczb całkowitych w kodzie
U2 -------------------------------------------------- a = -234 b = 576 -234 * 576 = -134784 Wynik prawidłowy |
Mnożenie 64-bitowych liczb całkowitych w kodzie
U2 -------------------------------------------------- a = -25675599 b = 557657657575 -25675599 * 557657657575 = 4128549678534539191 Wynik błędny, NADMIAR !!! |
Dzielenie liczb U2 jest zawsze dzieleniem całkowitoliczbowym i obowiązują tutaj te same zasady, co przy liczbach NBC:
Jeśli wykonujesz mnożenie i dzielenie liczb
całkowitych U2, dzielenie umieszczaj na końcu
wyrażenia. Nie dziel liczby na moduł mniejszej przez liczbę na moduł większą, gdyż w wyniku otrzymasz zawsze 0. |
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.
Przykładowy program w języku C++
// 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; } |
Wynik |
Przeliczanie pomiędzy stopniami Celsjusza i
Fahrenheita ------------------------------------------------------- Temperatura = 0 0°C = 32°F 0°F = -17°C |
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:
Xn + 1 = (aXn + c) mod m |
Gdzie:
Xn + 1 – następna liczba
pseudolosowa Xn – poprzednia liczba pseudolosowa a – mnożnik c – przyrost m – moduł |
W funkcji występuje działanie modulo, czyli reszta z dzielenia dwóch liczb całkowitych. W języku C++ realizuje je operator arytmetyczny %:
5 % 3 = 2, ponieważ 3 mieści się w 5 jeden raz i zostaje reszta 2. |
Następna liczba pseudolosowa Xn + 1 powstaje z liczby poprzedniej Xn. Oznacza to, iż liczby te nie są dowolne, lecz tworzą ciąg:
X0 X1 X2 ... |
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:
X0 → X1 → X2 → ... Xm - 2 → Xm - 1 → X0 → X1 → ... |
Pierwszą liczbę X0 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:
Podsumujmy:
a = 27 c = 11 m = 26 |
Funkcja generatora ma wzór:
Xn + 1 = 87·(Xn + 11) mod 26 |
Jako X0 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.
Przykładowy program w języku C++
// 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; } |
Wyniki |
Przykładowy generator liczb pseudolosowych z
zakresu od 0 do 25 --------------------------------------------------------------- X0 = 0 11 22 7 18 3 14 25 10 21 6 17 2 13 24 9 20 5 16 1 12 23 8 19 4 15 0 |
Przykładowy generator liczb pseudolosowych z
zakresu od 0 do 25 --------------------------------------------------------------- X0 = 10 21 6 17 2 13 24 9 20 5 16 1 12 23 8 19 4 15 0 11 22 7 18 3 14 25 10 |
Przykładowy generator liczb pseudolosowych z
zakresu od 0 do 25 --------------------------------------------------------------- X0 = 20 5 16 1 12 23 8 19 4 15 0 11 22 7 18 3 14 25 10 21 6 17 2 13 24 9 20 |
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.
Przykładowy program w języku C++
// 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; } |
Wynik |
Wbudowany generator liczb pseudolosowych ---------------------------------------- 41 18467 6334 26500 19169 15724 11478 29358 26962 24464 |
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.
Przykładowy program w języku C++
// 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; } |
Wyniki |
Ziarno wbudowanego generatora liczb
pseudolosowych -------------------------------------------------- Podaj ziarno pseudolosowe od 0 do 32767 X0 = 0 38 7719 21238 2437 8855 11797 8365 32285 10450 30612 |
Ziarno wbudowanego generatora liczb
pseudolosowych -------------------------------------------------- Podaj ziarno pseudolosowe od 0 do 32767 X0 = 1 41 18467 6334 26500 19169 15724 11478 29358 26962 24464 |
Ziarno wbudowanego generatora liczb
pseudolosowych -------------------------------------------------- Podaj ziarno pseudolosowe od 0 do 32767 X0 = 2 45 29216 24198 17795 29484 19650 14590 26431 10705 18316 |
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ć
Przykładowy program w języku C++
// 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; } |
Wyniki |
Uprzypadkowienie wbudowanego generatora liczb
pseudolosowych ------------------------------------------------------------ 1519 12568 436 2376 30534 3152 10392 6205 14274 6661 |
Uprzypadkowienie wbudowanego generatora liczb
pseudolosowych ------------------------------------------------------------ 1711 24132 5846 13087 16501 5453 30186 30104 5418 4373 |
Uprzypadkowienie wbudowanego generatora
liczb pseudolosowych ------------------------------------------------------------ 1865 5019 26262 29951 9766 26169 12632 23594 27798 10326 |
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 (230 - 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:
Przykładowy program w języku C++
// 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; } |
Wyniki |
Rzuty kostką ------------ 1 3 2 5 5 2 5 1 4 1 5 5 3 4 4 3 6 5 4 3 6 6 3 6 1 5 5 1 3 2 2 6 2 5 3 5 |
Rzuty kostką ------------ 6 5 2 6 1 4 5 5 5 4 1 2 1 5 2 5 6 4 4 1 5 6 3 6 5 6 3 4 3 3 4 1 2 4 2 2 |
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:
default_random_engine | : | wybrany generator pseudolosowy, który daje dobre wyniki w typowych, prostych zastosowaniach. |
minstd_rand | : | prosty, liniowy generator
multiplikatywny LCG: x = x * 48271 % 2147483647 |
minstd_rand0 | : | prosty, liniowy generator
multiplikatywny LCG: x = x * 16807 % 2147483647 |
mt19937 | : | generator pseudolosowy typu Mersenne Twister. Daje w wyniku liczby 32-bitowe. |
mt19937_64 | : | generator pseudolosowy typu Mersenne Twister. Daje w wyniku liczby 64-bitowe. |
ranlux24_base | generator pseudolosowy typu Ranlux o podstawie 24-bitowej. Daje w wyniku liczby 32-bitowe. | |
ranlux48_base | generator pseudolosowy typu Ranlux o podstawie 48-bitowej. Daje w wyniku liczby 64-bitowe. | |
ranlux24 | generator pseudolosowy typu Ranlux o podstawie 24-bitowej z przyspieszonym postępem. Daje w wyniku liczby 32-bitowe. | |
ranlux48 | generator pseudolosowy typu Ranlux o podstawie 48-bitowej z przyspieszonym postępem. Daje w wyniku liczby 64-bitowe. | |
knuth_b | generator pseudolosowy typu Knuth-B. Daje w wyniku liczby 32-bitowe. |
Każda klasa generatora posiada funkcje składowe:
(konstruktor) | : | tworzy obiekt danej klasy i inicjuje jego elementy składowe, tak aby był gotowy do użytku. Jako parametr dla konstruktora przekazuje się ziarno typu całkowitego bez znaku. |
min() | : | zwraca minimalną wartość generowanych liczb pseudolosowych. |
max() | : | zwraca maksymalną wartość generowanych liczb pseudolosowych. |
seed(v) | inicjuje na nową wartość wewnętrzne ziarno pseudolosowe wg wartości v. | |
operator() | generuje kolejną liczbę pseudolosową i zwraca ją jako wynik operatora nawiasy (). | |
discard() | generuje kolejną liczbę pseudolosową, lecz nie zwraca jej. |
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.
Przykładowy program w języku C++
// 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; } |
Wynik |
Zakresy bibliotecznych generatorów
pseudolosowych ------------------------------------------------- standardowy : 1 ... 2147483646 multiplikatywny LCG : 1 ... 2147483646 multiplikatywny LCG 0: 1 ... 2147483646 Mersenne Twister : 0 ... 4294967295 Mersenne Twister 64 : 0 ... 18446744073709551615 Ranlux 24-bitowy : 0 ... 16777215 Ranlux 48-bitowy : 0 ... 281474976710655 |
Następny program generuje 15 liczb pseudolosowych za pomocą wybranego generatora pseudolosowego. Generator możesz zmienić na inny.
Przykładowy program w języku C++
// 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; } |
Wynik |
Generacja liczb pseudolosowych generatorem
Mersenne Twister ---------------------------------------------------------- 10537470712149690863 16289189653767349705 17446861035845780457 8462092411226512412 11670304320697365710 89603159830766338 11893928287530825151 4391792179446479643 5359857403735253840 939567318540422672 1708525228151313803 7177467170986783977 12812186784476095291 9706571523780530581 17589396534050711681 |
Jeśli chcesz otrzymywać liczby z zakresu A...B, to możesz zastosować podany wcześniej wzór:
A = generator() % (B - A + 1) |
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:
Poniższy program generuje 200 liczb pseudolosowych o rozkładzie jednorodnym.
Przykładowy program w języku C++
// 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; } |
Wynik |
200 liczb pseudolosowych od 1 do 999 o
rozkładzie jednorodnym ------------------------------------------------------------- 573 919 35 724 241 623 106 20 82 683 348 233 137 86 408 63 412 421 587 607 258 98 355 342 460 672 321 263 826 787 566 971 51 926 816 717 123 672 934 280 408 420 474 933 267 81 139 854 987 419 480 307 248 827 297 164 85 819 579 958 700 226 399 256 436 158 283 405 259 162 122 32 698 944 703 57 552 928 498 45 951 516 167 871 772 782 119 133 770 156 788 844 272 726 856 927 678 644 892 503 124 696 332 919 855 357 369 751 227 387 956 786 707 827 193 582 829 395 10 11 861 638 255 437 80 473 237 53 380 314 874 728 443 586 624 196 813 612 530 778 965 817 821 334 548 610 647 386 437 806 781 806 756 60 961 360 142 748 270 435 143 857 623 427 801 409 388 656 922 956 252 54 40 442 825 103 297 195 91 642 191 549 537 140 565 425 247 305 938 687 132 996 955 424 24 668 189 463 479 275 |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.