Liczby naturalne

Liczby naturalne

grafika

Gottfried Wilhelm von Leibniz (1646–1716)

System dwójkowy, zbadany i spopularyzowany przez Wilhelma Gotfrieda Leibniza w wieku XVII, ma wiele zalet. Podobnie jak w dziesiętnym systemie pozycyjnym, liczby naturalne przedstawiamy jako sumę potęg bazy (2) z odpowiednimi wagami reprezentowanymi przez cyfry – w tym przypadku tylko dwie: 0 i 1. Każda liczba naturalna dodatnia ma zatem reprezentację postaci
\( \sum_{k=0}^{m} a_k2^k \), gdzie \( a_k\in\{0,1\} \).
Reprezentacja ta jest jednoznaczna, jeśli przyjmiemy, że nie stosujemy wiodących zer. Warto zapamiętać pierwszych 16 wartości:

Jeśli ustalimy z góry pewną liczbę \( n \) cyfr, za pomocą których będziemy reprezentowali liczby naturalne, to w automatyczny sposób uzyskamy \( n \)-cyfrowe reprezentacje, uzupełniając je do pełnych \( n \) cyfr zerami z lewej strony. Kolejno mielibyśmy np. dla \( n=8:00000000,00000001,00000010,\ldots,11111111 \). Widać, że różnych wartości \( n \)-cyfrowych jest \( 2^n \): od \( 0 \) do \( 2^n-1 \).
Jak w prosty sposób znajdować reprezentacje dwójkowe liczb naturalnych? Są dwie proste metody. Załóżmy, że chodzi nam o przedstawienie dwójkowe liczby \( m>0 \).

• Znajdujemy największą liczbę \( d=2^k \) nieprzekraczającą \( m \). Piszemy jedynkę, odejmujemy od \( m \) wartość \( d \), a następnie kolejno dla wszystkich mniejszych potęg dwójki sprawdzamy, czy mieszczą się one w tym, co zostało z \( m \). Jeśli dana potęga dwójki nie mieści się, to dopisujemy zero, a jeśli mieści się, to dopisujemy jedynkę i odejmujemy tę wartość od tego, co zostało z \( m \). Przykładowo dla \( m=13: \)

• Zaczynamy od liczby \( m \), a następnie dopóki m jest większe od zera dzielimy \( m \) przez 2, zapisując kolejno otrzymywane reszty. Ciąg reszt odczytany od końca da nam poszukiwaną reprezentację. Przykładowo dla tego samego \( m=13: \)

Ciąg reszt z ostatniej kolumny czytany od dołu do góry daje właśnie \( 1101 \), czyli reprezentację dwójkową \( 13 \).
W odwrotną stronę trudno podać lepszą metodę niż proste dodanie kolejnych potęg dwójki, zatem np. 10101, to
\( 1\cdot 16+0\cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1\cdot 1=21 \).
Teoretycznie jesteśmy więc w stanie reprezentować każdą liczbę naturalną. Musimy jednak zdać sobie sprawę z tego, że to jest tylko ułuda. W rzeczywistości trzeba by mieć nieograniczoną pamięć, aby reprezentować bardzo duże liczby, a w każdym komputerze, ba, we wszystkich komputerach świata łączna pamięć jest i będzie ograniczona i skończona. Musimy zatem pogodzić się z tym, że będziemy w stanie reprezentować jedynie skończony podzbiór liczb naturalnych. Zazwyczaj robi się to tak, że do reprezentacji liczb całkowitych używa się standardowo określonej z góry liczby bitów (typowo 8, 16, 32 lub 64). Jeżeli chcemy reprezentować liczby o większej długości, to musimy sami sobie to zaprogramować, ale i tak wszystkich liczb naturalnych nie będziemy w stanie wyrazić.
Z tych prostych uwag wynikają ważne wnioski. Po pierwsze może nam zabraknąć liczb do realizacji założonych celów. Po drugie, świat liczb naturalnych różni się od świata liczb naturalnych reprezentowanych w komputerze choćby tym, że nie wszystkie działania będą wykonalne. I to nie tylko chodzi o dzielenie. W szczególności, skoro zbiór liczb reprezentowanych w komputerze jest skończony, to istnieją w nim dwie największe i dodanie ich do siebie spowoduje, że wynik będzie niereprezentowalny.

Liczby całkowite

Liczby całkowite

Znak – moduł

Sposób ten jest bardzo naturalny. Spośród \( n \) dostępnych bitów wyróżniamy jeden – umówmy się, że pierwszy z lewej – i rezerwujemy go na określenie znaku liczby. Pozostałe \( n-1 \) bitów reprezentuje moduł liczby w tradycyjny sposób omówiony powyżej. Jeśli pierwszy bit znaku jest równy \( 0 \), to liczba jest nieujemna, a jeśli \( 1 \), to jest niedodatnia.

Oto tabela 16 liczb 4-bitowych zakodowanych tą metodą:

Kod znak – moduł
Zauważmy, że podane kodowanie prowadzi do dość dziwnej sytuacji, że zero reprezentujemy na 2 sposoby: nieujemne zero (0000) i niedodatnie zero (1000). To dość duża wada tego systemu kodowania; w szczególności trzeba uważać porównując wartości dwóch liczb, żeby nie stwierdzić, że \( 0\neq-0 \), o co bardzo łatwo porównując tradycyjnie bit po bicie zawartości bitowe takich reprezentacji.

W kodzie tym dla liczb \( n \)-bitowych mamy zakres \( -2^{n-1}+1\ldots 2^{n-1}-1 \) i różnych liczb reprezentowanych jest w związku z tym \( 2^n-1 \).

Znak – moduł odwrotny

Sposób ten jest bardzo podobny do poprzedniego. Tak samo pierwszy bit oznacza znak, ale jeśli pierwszy bit jest 1 (co oznacza liczbę niedodatnią), to pozostałe \( n-1 \) bitów reprezentuje negatyw modułu liczby. Podobnie, jak poprzednio, jeśli pierwszy bit znaku jest równy \( 0 \), to liczba jest nieujemna, a jeśli \( 1 \), to jest niedodatnia.

Oto tabela 16 liczb 4-bitowych zakodowanych tą metodą w kodzie znak – moduł odwrotny:

Kod znak – moduł odwrotny
Zauważmy, że liczby nieujemne są reprezentowane dokładnie w taki sam sposób jak poprzednio, oraz że i tu podane kodowanie prowadzi do podwójnej reprezentacji zera. W kodzie tym dla liczb \( n \)-bitowych mamy ten sam zakres \( -2^{n-1}+1\ldots 2^{n-1}-1 \) i różnych liczb reprezentowanych jest w związku z tym \( 2^n-1 \).
Po co sobie utrudniać kodowanie przez branie odwrotności modułu? Okazuje się, że system ten jest wygodniejszy, przynajmniej jeśli chodzi o dodawanie. W systemie znak-moduł, aby dodać dwie liczby przeciwnych znaków trzeba by najpierw ustalić znak wyniku i zdecydować, od którego modułu odjąć który. Okazuje się, że w kodzie znak-moduł odwrotny wystarczy, nie przejmując się znakami, dodać bitowo reprezentacje i, jeśli ostatecznie pojawi się w przeniesieniu całego wyniku jedynka, dodać ją jeszcze raz do otrzymanego rezultatu.
Przykładowo dodajmy w kodzie znak-moduł odwrotny \( -4 \) do \( 6 \). Otrzymamy

     1011
     0110 
     -- --- 
(1)  0001

i teraz jedynkę przeniesienia \( (1) \) dodajemy do wyniku 0001 i otrzymujemy 0010, czyli reprezentację dwójki, czyli prawidłowego wyniku.

Kod uzupełnieniowy

Jest to najczęściej stosowany kod. Ma bardzo prostą interpretację – po prostu najstarszy bit \( n \)-bitowej reprezentacji traktujemy jako \( -2^{n-1} \), a pozostałe tradycyjnie jako wartości, kolejno \( 2^{n-2},\ldots,2^0 \). Popatrzmy, jak wygląda nasza tabela czterobitowych wartości zapisanych w kodzie uzupełnieniowym. Kolejno od lewej bity nają wartości \( -8,4,2,1 \).Z trzech młodszych bitów generujemy wszystkie wartości od 0 do 7, a jeśli włączymy bit \( -8 \), to dodanie do niego tych wartości da nam liczby od \( -8 \) do \( -1 \).

Kod uzupełnieniowy
W n-bitowym kodzie uzupełnieniowym mamy następujące własności:

• Wartości są z przedziału \( [-2^{n-1},2^{n-1}-1] \)
• Każda wartość jest reprezentowana jednoznacznie
• Liczb ujemnych jest o jeden więcej niż dodatnich
• \( 000\ldots 0 \) to zawsze \( 0 \), a \( 111\ldots 1 \) to zawsze \( -1 \)

Kod uzupełnieniowy ma jeszcze jedną miłą cechę: dodawanie w nim nie wymaga żadnych specjalnych czynności. Po prostu dodaje się bitowo reprezentacje i jeśli pojawia się bit przepełnienia, to się go ignoruje. Na przykład: jeśli chcemy dodać \( -4 \) do \( 6 \), to w naszym 4-bitowym systemie dostaniemy

     1100 (-4)
     0110 (6) 
     -- --- 
(2)  0010

Od tej pory, jeśli wyraźnie tego nie zaznaczymy, to będziemy używali reprezentacji uzupełnieniowej. Zapamiętajmy. Uwaga
We wszystkich stosowanych systemach liczby dodatnie reprezentuje się identycznie.
Powstaje jeszcze jeden problem. Co się dzieje, jeśli w wyniku wykonania jakiegoś działania wynik wyjdzie spoza zakresu reprezentowalności? Oczywiście cudów nie ma. Musimy pogodzić się z tym, że jakkolwiek to ustalimy, zawsze będzie możliwa taka właśnie sytuacja, że pewnych liczb, będących legalnymi wynikami działań, przedstawić się nie da. Mówimy w takiej sytuacji o problemie przepełnienia i uznajemy ją za błędną. Warto pamiętać jednak o jednej niezwykle istotnej rzeczy: niektóre systemy komputerowe nie zauważają sytuacji przepełnienia i wtedy może zajść dziwna sytuacja, w której np. dodanie dwóch liczb dodatnich daje ujemny wynik. Oto przykładowo w naszej reprezentacji 4-bitowej spróbujmy dodać \( 4 \) do \( 6 \). dostaniemy

     0100   (4)
     0110   (6) 
     -- --- 
 (0) 1010 (-6) 
<code> 
 
<p>Bit przeniesienia jest równy 0, ale wynik jest absurdalny. Czegóż innego jednak można się było spodziewać? Przecież liczby 10 nie umiemy w naszym czterobitowym systemie wyrazić. W rzeczywistości dodanie jedynki do największej liczby dodatniej w kodzie uzupełnieniowym (czyli do \( 0111\ldots 1 \) daje nam najmniejszą liczbę ujemną, czyli \( 1000\ldots 0 \), zatem cały reprezentowany przedział się w ten sposób zacykla. Te same uwagi dotyczą rzecz jasna innych działań. Rozpoznać sytuację przepełniania można automatycznie i wiele systemów to robi, ale są środowiska programistyczne, które przechodzą nad tym problemem do porządku dziennego i wykonują błędnie działania bez kontroli przepełnienia. </p>

Ułamki

Ułamki

Zacznijmy od reprezentacji binarnej ułamków. Podobnie jak w systemie dziesiętnym korzystamy z ujemnych potęg dziesiątki po przecinku, tak tu będziemy rozważali binarne rozwinięcia ułamków za pomocą ujemnych potęg dwójki. Zatem po kropce binarnej, oddzielającej część całkowitą od ułamkowej, kolejne pozycje będą odpowiadały bitom reprezentującym kolejno wartości \( \frac{1}{2},\frac{1}{4},\frac{1}{8},\ldots \). Liczba \( \frac{1}{2} \) będzie zatem miała przedstawienie \( 0.1 \), liczba \( \frac{1}{4} \) będzie miała przedstawienie \( 0.01 \), liczba \( \frac{3}{4} \) będzie miała przedstawienie \( 0.11 \) itd. Wszystko jest proste, jeśli w mianowniku ułamka są potęgi dwójki. Wystarczy bowiem zapisać licznik binarnie, a następnie kropkę binarną przesunąć w prawo o tyle pozycji, ile wynosi potęga dwójki w mianowniku. Na przykład \( \frac{5}{16} \) ma przedstawienie \( 0.0101 \): jest to po prostu \( 5 \) czyli \( 101 \) przesunięte o 4 pozycje w prawo.

Co jednak począć z mianownikami niebędącymi potęgami dwójki? W systemie dziesiętnym mamy podobny problem. Jeśli jedynymi dzielnikami mianownika są \( 5 \) i \( 2 \), to otrzymujemy skończone rozwinięcie ułamka. W przeciwnym razie rozwinięcia są nieskończone i dla liczb wymiernych okresowe (można się umówić, że wszystkie rozwinięcia liczb wymiernych są okresowe, tylko niektóre mają okres złożony z samego zera!).

Jak zatem znajdować binarne rozwinięcia ułamków wymiernych? Oto algorytm, którego nieskomplikowany (ale i nieoczywisty) dowód poprawności można przeprowadzić indukcyjnie, i który działa również dla systemu dziesiętnego (oczywiście rolę dwójki pełni tam dziesiątka) – proszę sprawdzić.

Algorytm przedstawiania ułamka \( u \) w binarnym systemie pozycyjnym. 
Założenie: \( 0\le u  < 1 \). 
Napisz \( 0 \).. Kolejne cyfry rozwinięcia binarnego będziemy generować w następujący sposób: 
Dopóki otrzymujesz nienapotkane wcześniej wartości \( u \) wykonuj 
1. Pomnóż \( u \) przez 2 
2. Jeżeli otrzymana wartość jest mniejsza od 1, to dopisz cyfrę \( 0 \) 
3. Jeżeli otrzymana wartość jest równa co najmniej 1, dopisz cyfrę  \( 1 \) i odejmij od wyniku 1. Z chwilą, gdy powtórzy się wartość \( u \), zakończ procedurę; wypisany ciąg jest okresowy, a jego okresem jest ciąg bitów między powtórzeniami.

Binarne rozwinięcie \( \frac{2}{7}=0.(010) \)

Widzimy, że \( \frac{2}{7} \) ma rozwinięcie binarne \( 0.010010010\ldots \). Okresem jest \( (010) \).
Spróbujmy znaleźć jeszcze rozwinięcie binarne dla \( \frac{1}{10} \).

Binarne rozwinięcie \( \frac{1}{10}=0.0(0011) \)

Zauważmy jeden wstrząsający fakt: nawet tak prosta liczba jak \( \frac{1}{10} \) ma nieskończone binarne rozwinięcie okresowe. Oczywiście takie rozwinięcia mają także \( \frac{2}{10},\frac{3}{10},\frac{4}{10}\frac{6}{10}\frac{7}{10},\frac{8}{10}\frac{9}{10} \). I rzeczywiście, gdy chcemy w komputerze (a nawet w kalkulatorach) reprezentować \( \frac{1}{10} \), jesteśmy zmuszeni do zaokrąglenia tej wartości i w rzeczywistości otrzymujemy tylko coś koło jednej dziesiątej. Przynajmniej tak to widzi komputer.

Zaokrąglenie

Zaokrąglenie

Kolejne zaokrąglenia \( \frac{1}{10} \)

To, co uzyskujemy, postępując w pokazany sposób, jest ciągiem najlepszych przybliżeń zadanej wartości za pomocą ułamków o mianownikach będących kolejnymi potęgami dwójki. W przypadku jednej dziesiątej są to kolejno \( \frac{0}{2},\frac{0}{4},\frac{1}{8},\frac{2}{16},\frac{3}{32},\frac{6}{64},\frac{13}{128},\frac{26}{256},\frac{51}{512} \). Nie ma liczników, które przy tych mianownikach lepiej przybliżałyby \( \frac{1}{10} \).

Doszliśmy do momentu, w którym trzeba podjąć wyjątkowo ważną decyzję. Musimy określić, ile bitów będziemy potrzebowali na część całkowitą, a ile na część ułamkową przybliżenia liczby rzeczywistej. Decyzja wcale nie jest łatwa, szczególnie że komputerów używają ludzie potrzebujący zarówno operować liczbami bardzo małymi, jak i bardzo dużymi. Weźmy choćby fizyków kwantowych – ci działają na wielkościach rzędu \( 10^{-34} \). Astrofizycy z kolei używają wielkości astronomicznych; promień Wszechświata choćby to jest wielkość rzędu \( 10^{23}m \). Gdybyśmy chcieli zadowolić i jednych i drugich, trzeba by dysponować mniej więcej 70 bitami na część całkowitą i ponad setką bitów na część ułamkową. Łącznie na każdą liczbę rzeczywistą, biorąc pod uwagę pewien zapas, trzeba by przeznaczyć pewnie około 200 bitów, czyli 25 bajtów. Znając życie, skończyłoby się na 32 bajtach.

Warto zauważyć przy tym, że astronomowie w ogóle nie byliby zainteresowani tymi częściami ułamkowymi, a kwantowcy tymi całkowitymi. W ich obliczeniach na tych pozycjach stałyby zera i komputery niepotrzebnie mieliłyby zerowe bity przy każdych działaniach. Biorąc pod uwagę to, że choćby mnożenie (nie mówiąc o bardziej skomplikowanych procedurach liczących pierwiastki, sinusy czy logarytmy) tradycyjną metodą wymaga przemnożenia każdego bitu przez każdy, co oznaczałoby \( 40000 \) mnożeń jednobitowych na każdą parę liczb rzeczywistych. Tym niemniej w niszowych zastosowaniach można stosować układ nazywany stałopozycyjnym.
Uwaga
W układzie stałopozycyjnym z góry określamy, ile bitów przeznaczamy na część całkowitą (k), a ile na ułamkową (u). Cały przedział określoności rozciąga się między \( -2^{k-1} \) a \( 2^{k-1}-2^{-u} \) i wartości w nim reprezentowane są równomiernie rozłożone co \( 2^{-u} \).

System zmiennopozycyjny

System zmiennopozycyjny

Musimy rozwiązać jeszcze jeden mały problem. Sposobów przedstawienia konkretnej wartości jest nieskończenie wiele. Na przykład liczbę \( \frac{3}{8} \) można przedstawić jako

\( \frac{3}{8}\cdot 2^0 = \frac{3}{4}\cdot 2^{-1} = \frac{3}{2}\cdot 2^{-2}= 3\cdot 2^{-3} = \ldots \)
i podobnie w drugą stronę:
\( \frac{3}{8}= \frac{3}{16}\cdot 2^{1} = \frac{3}{32}\cdot 2^{2}= \ldots \).
Niewygodne byłoby używać kilku reprezentacji tej samej wartości. Stąd pomysł, żeby wybrać jedną z nich jako standardową i zapamiętywać wartości w takiej znormalizowanej postaci. Powszechnie przyjmuje się, że dobieramy tak mantysę, aby jej wartość mieściła się w przedziale \( (\frac{1}{2},1] \) dla wartości dodatnich oraz \( [-1,-\frac{1}{2}) \) dla wartości ujemnych. Zero reprezentuje się w specyficzny sposób i zajmiemy się tym problemem później.
Podsumujmy zatem nasze ustalenia.

Każdą niezerową liczbę rzeczywistą reprezentujemy za pomocą przybliżenia wymiernego w postaci 
pary \( (m,c) \), gdzie \( m\in[-1,-\frac{1}{2})\cup[\frac{1}{2},1) \) jest mantysą, 
zaś \( c \), nazywane cechą, określa o ile pozycji w prawo (dla \( c \) ujemnych) bądź w lewo (dla \( c \) dodatnich) należy przesunąć mantysę,  aby uzyskać żądaną wartość. Interpretacja takiej reprezentacji wyraża się wzorem 
\( x=m2^c \)

System o 3 bitach cechy i 4 mantysy

Zero

Zero

Ukrywanie bitu

Ukrywanie bitu

Częstym rozwiązaniem jest też oszczędzanie jednego bitu na drugiej pozycji. Skoro znak liczby determinuje kolejny bit (musi być przeciwny), to nie ma sensu go osobno pamiętać. Zatem reprezentując liczby po bicie znaku mamy od razu bit 1/4 i tylko pamiętamy, że ukryty bit dotyczy wartości 1/2. Przy omówieniu naszego systemu tego aspektu nie braliśmy pod uwagę. Wszystkie wnioski, które wyciągnęliśmy przenoszą się również na system z ukrytym bitem.

Dodawanie w systemie zmiennopozycyjnym

NIE TYLKO ZERO NIE ZMIENIA WARTOŚCI DRUGIEGO ARGUMENTU PRZY DODAWANIU!

DODAWANIE ZMIENNOPOZYCYJNE NIE JEST ŁĄCZNE!

Projektując szybkie algorytmy nie tylko przyspieszamy rozwiązywanie problemów, ale przy okazji ograniczamy
możliwości nawarstwiania się błędów. Szybkie algorytmy nie mają czasu zrobić zbyt 
dużych błędów!

Ćwiczenia