WDP Reprezentacja liczb

<<< Powrót

Wcale nie jest oczywiste, jak należy reprezentować liczby w komputerze. Powszechnie wiadomo, że bardzo wygodny technologicznie jest układ dwójkowy, zwany też binarnym. Łatwiej jest bowiem reprezentować i rozróżniać dwie wartości, niż jakąkolwiek większą ich liczbę: wystarczy przecież rozróżnić "brak sygnału" od "jest sygnał", żeby reprezentować dwie cyfry binarne. Jakakolwiek próba zwiększenia liczby cyfr, które trzeba by było rozróżniać, wymusiłaby analizę ilościową sygnału, a nie tylko jakościową.

Liczby naturalne

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_{k}2^{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:

$k$	$(k)_{2}$
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...	0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

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

zostało z $m$	potega dwójki	wypisano
13 5 1 1 0	8 4 2 1	1 11 110 1101

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

zostało z $m$ po dzieleniu przez 2	reszta z dzielenia $m$ przez 2
13 6 3 1 0	1 0 1 1

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 zatem jesteśmy 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

Umówmy się zatem, że przeznaczymy określoną liczbę $n$ bitów, aby reprezentować liczby całkowite. Powstaje pytanie, jak zapisywać liczby ujemne? Istnieją co najmniej trzy sposoby, stosowane zresztą przez producentów różnych procesorów do dziś. Pokrótce je omówimy.

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

bity	wartość
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	0 1 2 3 4 5 6 7 -0 -1 -2 -3 -4 -5 -6 -7

Kod znak – moduł

Zauważmy, że podane kodowanie prowadzi do dziwnej dość sytuacji, że zero reprezentujemy na 2 sposoby: nieujemne zero (0000) i niedodatnie zero (1000). To jest 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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 0} , to liczba jest nieujemna, a jeśli Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1} , to jest niedodatnia.

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

bity	wartość
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	0 1 2 3 4 5 6 7 -7 -6 -5 -4 -3 -2 -1 -0

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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n} -bitowych mamy ten sam zakres Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle -2^{n-1}+1\ldots 2^{n-1}-1} i różnych liczb reprezentowanych jest w związku z tym Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle -4} do Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 6} . Otrzymamy

     1011
     0110
     -- ---
(1)  0001

i teraz jedynkę przeniesienia Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n} -bitowej reprezentacji traktujemy jako Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle -2^{n-1}} , a pozostałe tradycyjnie jako wartości, kolejno Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 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$.

bity	wartość
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	0 1 2 3 4 5 6 7 -8 -7 -6 -5 -4 -3 -2 -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)

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.

Ułamki

Jak reprezentować liczby rzeczywiste? W tym przypadku mamy jeszcze większy problem, gdyż nie dość, że jest ich nieskończenie wiele, nie dość, że tworzą zbiór gęsty, to jeszcze jest ich nieprzeliczalnie wiele. Stoimy zatem przed problemem, jak wybrać skończony ich podzbiór tak, żeby jak najlepiej reprezentował nasze potrzeby. Działania, które będziemy wykonywali dadzą wyniki tylko w ramach tego podzbioru, więc może się zdarzyć, że wynik będzie odbiegał od rzeczywistości. Fenomen ten znamy dobrze z doświadczeń z kalkulatorami: zwykle, jeśli najpierw podzielimy jedynkę przez trzy, a potem pomnożymy wynik przez 3, otrzymamy coś w rodzaju $0,99999999$. Błąd się wziął stąd, że w zestawie wartości niereprezentowanych przez kalkulator brakuje jednej trzeciej. Zamiast niej mamy jej przybliżenie $0,33333333$, które pomnożone przez $3$ daje właśnie to, co widzimy na wyświetlaczu. Dzieje się tak nie tylko dlatego, że kalkulatory są prymitywnymi urządzeniami. Duże komputery cierpią na te same dolegliwości (choć akurat powyższe działanie mogą wykonać lepiej). Zajmiemy się teraz doborem właściwego podzbioru reprezentującego liczby rzeczywiste (a tak naprawdę wymierne, bo to takich wartości nasz podzbiór się będzie ograniczał).

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 prosto, 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\leq 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 no 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.  

bity	wartość
0 0 0 1 0	${\frac {2}{7}}$ ${\frac {4}{7}}$ ${\frac {1}{7}}$ ${\frac {2}{7}}$

Binarne rozwinięcie ${\frac {2}{7}}$

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}}$.

bity	wartość
0. 0 0 0 1 1	${\frac {1}{10}}$ ${\frac {2}{10}}$ ${\frac {4}{10}}$ ${\frac {8}{10}}$ ${\frac {6}{10}}$ ${\frac {2}{10}}$

Binarne rozwinięcie ${\frac {1}{10}}$

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

Skoro nie da się dokładnie reprezentować wartości wymiernych w komputerze, trzeba się pogodzić z ich przybliżaniem. Robimy to za pomocą zaokrąglania, przy czym reguły są bardzo proste: jeżeli mamy ochotę zaokrąglić na $k$-tej pozycji, to patrzymy się na następną cyfrę i jeśli jest ona zerem, to po prostu cały ogon odrzucamy (zaokrąglenie w dół), a jeśli jest jedynką, to dodajemy ją do uciętego na $k$-tym miejscu przybliżenia (zaokrąglenie w górę). Oto kolejne przybliżenia ${\frac {1}{10}}$ w zależności od stopnia dokładności, czyli określenia, ile cyfr po kropce binarnej chcemy mieć.

Numer bitu zaokrąglenia	reprezentacja
1 2 3 4 5 6 7 8 9 ...	0.0 0.00 0.001 0.0010 0.00011 0.000110 0.0001101 0.00011010 0.000110011

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}$.

We współczesnych komputerach właściwie bez wyjątku spotykamy inną metodę zapisu liczb rzeczywistych. Pomysł zaczerpnięto od fizyków właśnie, którzy nie kwapią się, aby używać tak niewygodnej jak stałopozycyjna notacji, po to, żeby np. wyrazić wielkości typu stałej Plancka. Wielkość ta, zapisana w dziesiętnej notacji stałopozycyjnej, wygląda mniej więcej tak: $h=0,000000000000000000000000000000000602Js$. Gdyby podręczniki mechaniki kwantowej zawierały tak zapisywane wielkości kwantowe, byłyby nieczytelne. Zamiast takiego zapisu stosuje się znacznie poręczniejszy: $6,02\cdot 10^{-34}Js$. W zapisie tym podajemy kilka cyfr znaczących oraz określamy rząd wielkości poprzez podanie, o ile należy je przesunąć w lewo lub w prawo. Przy takim przedstawieniu cyfry znaczące nazywamy mantysą, a potęgę podstawy obrazującą, o ile należy przesunąć przecinek dziesiętny - cechą. Umówmy się ponadto, że w przypadku zapisów binarnych będziemy używali znaku kropki dla oddzielenia części całkowitej od ułamkowej i nazywali go kropką binarną.

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.

Uwaga

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}$

Pozostaje nam zatem umówić się, ile bitów przeznaczymy na mantysę, a ile na cechę. Typowe wartości to $(m=52,c=12)$, $m=40,c=8$. Dla celów ilustracyjnych przyjmijmy, że $m=4,c=3$ i zobaczmy dokładnie, jak wygląda arytmetyka zmiennopozycyjna w tym mocno okrojonym zakresie. Mamy więc 8 różnych cech i 8 różnych mantys: 4 dodatnie i 4 ujemne – zauważmy, że warunki narzucone na mantysy ograniczają nam swobodę układania bitów, stąd gubimy jeden stopień swobody. Spodziewamy się więc możliwości przedstawienia $64$ różnych liczb niezerowych.

Przyjmujemy zatem uzupełnieniową reprezentację cechy i mantysy. Bity cechy mają zatem kolejno wartości $-4,2,1$, a bity mantysy kolejno $-1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}}$. Przykładowo liczba ${\frac {3}{8}}$ ma zatem przedstawienie dokładne $111\ \ 0110$, czyli

$c=-4+2+1=-1,m={\frac {1}{2}}+{\frac {1}{4}}={\frac {3}{4}}$.

Spróbujmy znaleźć reprezentację liczby ${\frac {2}{11}}$. Zaczynamy od zamiany tej liczby na system binarny, otrzymując kolejno bity $0.001011\ldots$. Tu możemy już przerwać, mimo że jeszcze nie trafiliśmy okresu, gdyż i tak interesują nas tylko $3$ bity od wystąpienia pierwszej jedynki, a czwarty bit rozważamy tylko po to, żeby uzyskać stosowne zaokrąglenie. Po dodaniu ostatniej wyznaczonej jedynki do reszty, czyli zaokrągleniu do $3$ znaczących cyfr, dostajemy liczbę $0.00110$, czyli ${\frac {3}{16}}$. Normalizujemy ją, przesuwając o 2 pozycje w lewo, czyli mnożymy przez $2^{2}$, więc ostatecznie dostajemy $110\ \ 0110$. Cecha jest oczywiście równa $-2$ - niweluje efekt przesunięcia o 2 pozycje. Zatem liczba ${\frac {3}{16}}=2^{-2}\cdot {\frac {3}{4}}$ najlepiej przybliża ${\frac {2}{11}}$ w naszym systemie, i ją właśnie przyjmujemy jako właściwego reprezentanta. Błąd względny, który przy tym popełniamy jest równy

${\frac {|{\frac {2}{11}}-{\frac {3}{16}}|}{\frac {2}{11}}}={\frac {1}{32}}$.

Przyjrzyjmy się teraz dokładnie wszystkim wartościom reprezentowanym w naszym systemie. Zacznijmy od cechy 0 i mantys dodatnich. Są tylko $4$ legalne dodatnie mantysy:

cecha	mantysa	wartość
000 000 000 000	0100 0101 0110 0111	${\frac {4}{8}}$ ${\frac {5}{8}}$ ${\frac {6}{8}}$ ${\frac {7}{8}}$

Dla cechy $1$ wartości te mnożą się przez 2:

cecha	mantysa	wartość
001 001 001 001	0100 0101 0110 0111	${\frac {4}{4}}$ ${\frac {5}{4}}$ ${\frac {6}{4}}$ ${\frac {7}{4}}$

... i dalej dla cech 3 i 4:

cecha mantysa wartość 010 010 010 010 0100 0101 0110 0111 ${\frac {4}{2}}$ ${\frac {5}{2}}$ ${\frac {6}{2}}$ ${\frac {7}{2}}$

cecha mantysa wartość 011 011 011 011 0100 0101 0110 0111 ${\frac {4}{1}}$ ${\frac {5}{1}}$ ${\frac {6}{1}}$ ${\frac {7}{1}}$

Mamy teraz następującą sytuację: \begin{rys.1} %Uwaga – przygotowuje go Wiesław Bartkowski ?? \end{rys 1} \podpis{rozmieszczenie liczb w systemie 3 bitów cechy i 4 mantysy dla cech nieujemnych i mantys dodatnich)

Zajmijmy się teraz cechami ujemnymi. Kolejne tabele pokazują wartości dla cech równych $-1,-2,-3,-4$.

dla cech równych -1 i -2:

cecha mantysa wartość 111 111 111 111 0100 0101 0110 0111 ${\frac {4}{16}}$ ${\frac {5}{16}}$ ${\frac {6}{16}}$ ${\frac {7}{16}}$

cecha mantysa wartość 110 110 110 110 0100 0101 0110 0111 ${\frac {4}{32}}$ ${\frac {5}{32}}$ ${\frac {6}{32}}$ ${\frac {7}{32}}$

oraz dla cech równych -3 i -4:

cecha mantysa wartość 101 101 101 101 0100 0101 0110 0111 ${\frac {4}{64}}$ ${\frac {5}{64}}$ ${\frac {6}{64}}$ ${\frac {7}{64}}$

cecha mantysa wartość 100 100 100 100 0100 0101 0110 0111 ${\frac {4}{128}}$ ${\frac {5}{128}}$ ${\frac {6}{128}}$ ${\frac {7}{128}}$

Uzyskaliśmy zatem całkiem niezłą rozdzielczość, którą w systemie stałopozycyjnym musielibyśmy okupić siedmiobitową częścią ułamkową.

Oto przedstawienie na osi mantys dodatnich z ujemnymi cechami: \begin{rys.2 %Uwaga – przygotowuje go Wiesław Bartkowski \end{rys 2 \podpis{rozmieszczenie liczb w systemie 3 bitów cechy i 4 mantysy dla cech ujemnych i mantys dodatnich)

Zauważmy, jakie własności ma uzyskane rozmieszczenie dokładnie reprezentowanych wartości. Po pierwsze, są one rozmieszczone nierównomiernie. Im dalej od zera tym rzadziej (dla cechy 3 wartości skaczą już o 1). W rzeczywistości w niektórych systemach nie są reprezentowane nawet wszystkie liczby całkowite mieszczące się w przedziale określoności; luki między nimi są większe niż 1. W każdym przedziale, odpowiadającym danej cesze, wszystkie wartości są rozmieszczone równomiernie; jest ich tyle, ile mantys danego znaku. W sąsiednim z prawej przedziale, odpowiadającym cesze większej o 1, jest tyle samo wartości rozmieszczonych jednak dwukrotnie rzadziej, a po lewej – odpowiadającym cesze o 1 mniejszej – dwukrotnie gęściej.

Ujemne liczby są rozmieszczone według tego samego schematu, tyle że zaczynają się od $-8$ i kolejne wartości to $-7,-6,-5,-{\frac {8}{2}},-{\frac {7}{2}},-{\frac {6}{2}}\ldots$.

Przyjrzyjmy się, jak wygląda dodawanie w naszym systemie. Dostając dwa argumenty, musimy pamiętać, żeby dodawane bity odpowiadały sobie wartościami. Trzeba zatem przed rozpoczęciem dodawania ujednolicić cechy, przesuwając o odpowiednią liczbę bitów jedną z mantys. I tu panuje zasada, że dostosowujemy mniejszą cechę do większej. Następnie wykonujemy dodawanie i normalizujemy wynik, na końcu go zaokrąglając. Prześledźmy te kroki na przykładzie. Dla uproszczenia przyjmijmy, że wychodzimy od argumentów reprezentowanych dokładnie.

Przykład 1

Zacznijmy od dodania ${\frac {3}{32}}+{\frac {3}{32}}$. Każda z tych liczb ma zapis $101\ \ 0110$. Cechy są równe, więc nie potrzeba niczego denormalizować. Wykonujemy dodawanie mantys otrzymując $1100$. Przesuwamy wynik o jeden w prawo – czyli dzielimy go przez 2 (tutaj otrzymujemy "naturalne" przepełnienie, które normalizując likwidujemy) i dodajemy do cechy 1. Wynik, to po prostu $110\ \ 0110$, czyli ${\frac {3}{16}}$. Zauważmy przy okazji, że mnożenie przez 2 i dzielenie przez 1 można wykonywać bezpośrednio dodając lub odpowiednio odejmując jedynkę od cechy!

Przykład 2

Dodajmy teraz ${\frac {3}{16}}$ do ${\frac {5}{2}}$. Reprezentacje bitowe w naszym systemie tych dwóch wartości to odpowiednio $110\ \ 0110$ (czyli $2^{-2}\cdot {\frac {3}{4}}$ oraz $010\ \ 0101$. Różnica w cechach to 4, więc o tyle bitów w prawo trzeba mantysę ?? ${\frac {3}{16}}$, aby jej bity podjechały pod odpowiadające im bity większego z argumentów. Załóżmy, ze na czas dodawania mamy pamięć na więcej bitów mantysy (cecha w czasie samego dodawania nie uczestniczy); tak się dzieje rzeczywiście: procesory mają dodatkowe bity – podwójną ich liczbę, którą wykorzystują w czasie wykonywania działań i dopiero po uzyskaniu możliwie dokładnego wyniku zaokrąglają go. Mamy zatem do dodania dwie mantysy: $0101$ oraz $0000110$. Wynikiem jest nieco przydługa mantysa $0101110$, której normalizować nie trzeba, bo jest w dobrej postaci, natomiast trzeba ją zaokrąglić na czwartym bicie. W efekcie zaokrąglenia dostajemy wynik postaci $010\ \ 0110$. Cecha bez zmian, a mantysa wskutek zaokrąglenia została powiększona o ${\frac {1}{8}}$. Ostatecznie zatem uzyskaliśmy $3$, która to liczba najlepiej przybliża u nas dokładny wynik, czyli ${\frac {43}{16}}$. Alternatywą było ${\frac {5}{2}}$, położone nieco dalej.

Przykład 3

Dodajmy teraz ${\frac {3}{32}}$, czyli $101\ \ 0110$ do ${\frac {5}{2}}$, czyli $010\ \ 0101$. Przykład ten robi się analogicznie do ostatniego, tyle że różnica między cechami wnosi obecnie 5, więc przesuwamy mantysę mniejszej liczby o 5 pozycji w prawo, otrzymując $00000110$. Ta mantysa, dodana do mantysy $0101$, daje $01010110$, która po zaokrągleniu nie wpływa na mantysę większej liczby. Liczba ${\frac {3}{32}}$, to jest za mały pikuś, żeby ${\frac {5}{2}}$ przy dodawaniu go zauważył! Zilustrowaliśmy właśnie ważny fenomen, który każdy informatyk powinien znać.

Uwaga

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

Dzieje się tak zawsze, gdy różnica cech argumentów przekracza o więcej niż jeden długość mantysy. Jest to pierwsza poważna różnica w stosunku do tradycyjnej algebry, do której jesteśmy przyzwyczajeni.

Drugą różnicę możemy wykryć, przyglądając się poprzednim przykładom. Jeśli będziemy wykonywali podwójne dodawanie ${\frac {5}{2}}+{\frac {3}{32}}+{\frac {3}{32}}$, to w przypadku, gdy zaczniemy wykonywać działania od lewej strony, dostaniemy zarówno po pierwszym, jak i po drugim dodawaniu ${\frac {5}{2}}$, ale gdy dodamy najpierw dwie mniejsze liczby ${\frac {3}{32}}+{\frac {3}{32}}$, a potem wynik tego dodawania ${\frac {3}{16}}$ do ${\frac {5}{2}}$, dostaniemy $3$, tak jak w przykładzie pierwszym. Oznacza to, że

Uwaga

DODAWANIE ZMIENNOPOZYCYJNE NIE JEST ŁĄCZNE.

Ćwiczenie

Który z uzyskanych wyników jest bliższy prawdziwemu?

Odpowiedź

{{{2}}}

Te dwie wskazane różnice między tradycyjną algebrą liczb wymiernych a arytmetyką komputerową trzeba znać. Nieznajomość pierwszej z nich prowadzi czasem do zapętlenia programu, kiedy oczekujemy, że ciąg rosnących wartości dotrze w końcu do pewnego oczekiwanego poziomu, którego się nigdy nie doczekamy, bo okazuje się, że stoimy w miejscu. Nieznajomość drugiej z nich wpływa na jakość obliczeń. Skoro wyniki można dostać różne, to znaczy, że zapewne któryś jest lepszy, a któryś gorszy. Jak wybrać najwłaściwszą kolejność? Przy dodawaniu dużej liczby wartości zawsze najlepiej zacząć od tych, które mają najmniejsze moduły – może z tych małych kawałeczków uzbiera sie coś godnego uwagi dla większych kolegów. Gdybyśmy zaczęli od argumentów o dużych różnicach cech, to mniejsze, żeby nie wiem ile ich było, mogą pozostać niezauważone przez większe.

Ćwiczenie

Zaprojektuj algorytm optymalnego dodawania $n$ argumentów.

Odpowiedź

{{{2}}}

Błędy zaokrągleń, powstające przy reprezentacji liczb a także przy wykonywaniu działań na nich, są na tyle ważnym zagadnieniem, że rozwinęły się w samodzielną dyscyplinę matematyczną – analizę numeryczną, która stanowi w naszym kursie osobny moduł. Zauważmy, że w miarę wykonywania serii obliczeń, błędy zaokrągleń kumulują się – na stare nakładają się nowe. Jeśli dobierzemy zły numerycznie algorytm, to wynik, wskutek nawarstwiania się błędów, może dowolnie daleko odjechać od autentycznego wyniku. Warto tu zapamiętać sobie jedną z motywacji porządnego programowania.

Uwaga

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!

Zatem dobry algorytm działa szybko i zazwyczaj generuje łącznie mniejsze błędy zaokrągleń.