Tekst źródłowy strony WDP Reprezentacja liczb

{{powrot|Wstęp do programowania|}}

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

[[Image:leibniz.jpg||thumb|right|200px|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 

<center><math>\sum_{k=0}^{m} a_k2^k</math>, gdzie <math>a_k\in\{0,1\}</math>.</center> 

Reprezentacja ta jest jednoznaczna, jeśli przyjmiemy, że nie stosujemy wiodących zer. Warto zapamiętać pierwszych 16 wartości: 
<table CELLPADDING=6 border=1 align=center>
<tr>
<td>&nbsp;&nbsp;<math>k</math>&nbsp;&nbsp;</td>
<td>&nbsp;&nbsp;<math>(k)_2</math>&nbsp;&nbsp;</td>
</tr>
<tr>
<td align=center>0<br>1<br>2<br>3<br>4<br>5<br>6<br>7<br>8<br>9<br>10<br>11<br>12<br>13<br>14<br>15<br>...</td>
<td align=right>0<br>1<br>10<br>11<br>100<br>101<br>110<br>111<br>1000<br>1001<br>1010<br>1011<br>1100<br>1101<br>1110<br>1111<br>&nbsp;</td>
</tr>
</table>
Jeśli ustalimy z góry pewną liczbę <math>n</math> cyfr, za pomocą których będziemy reprezentowali liczby naturalne, to w automatyczny sposób uzyskamy <math>n</math>-cyfrowe reprezentacje, uzupełniając je do pełnych <math>n</math> cyfr zerami z lewej strony. Kolejno mielibyśmy np. dla <math>n=8:00000000,00000001,00000010,\ldots,11111111</math>. Widać, że różnych wartości <math>n</math>-cyfrowych jest <math>2^n</math>: od <math>0</math> do <math>2^n-1</math>. 

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 <math>m>0</math>. 
*Znajdujemy największą liczbę  <math>d=2^k</math> nieprzekraczającą <math>m</math>. Piszemy jedynkę, odejmujemy od <math>m</math> wartość <math>d</math>, a następnie kolejno dla wszystkich mniejszych potęg dwójki sprawdzamy, czy mieszczą się one w tym, co zostało z <math>m</math>. 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 <math>m</math>. Przykładowo dla <math>m=13</math>:

<table CELLPADDING=6 border=1 align=center>
<tr>
<td>zostało z <math>m</math>&nbsp;&nbsp;</td>
<td>potega dwójki</td>
<td>wypisano</td>
</tr>
<tr>
<td align=right>13<br>5<br>1<br>1<br>0</td>
<td align=right>8<br>4<br>2<br>1<br>&nbsp;</td>
<td align=right>1<br>11<br>110<br>1101<br>&nbsp;</td>
</tr>
</table>

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

<table CELLPADDING=6 border=1 align=center>
<tr>
<td>zostało z <math>m</math> po dzieleniu przez 2</td>
<td>reszta z dzielenia <math>m</math> przez 2</td>
</tr>
<tr>
<td align=right>13<br>6<br>3<br>1<br>0</td>
<td align=right>1<br>0<br>1<br>1<br>&nbsp;</td>
</tr>
</table>

Ciąg reszt z ostatniej kolumny czytany od dołu do góry daje właśnie <math>1101</math>, czyli reprezentację dwójkową <math>13</math>. 

W odwrotną stronę trudno podać lepszą metodę niż proste dodanie kolejnych potęg dwójki, zatem np. 10101, to
<center><math>1\cdot 16+0\cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1\cdot 1=21</math>.</center>

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

Umówmy się zatem, że przeznaczymy określoną liczbę <math>n</math> 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 <math>n</math> dostępnych bitów wyróżniamy jeden – umówmy się, że pierwszy z lewej – i rezerwujemy go na określenie znaku liczby. Pozostałe <math>n-1</math> bitów reprezentuje moduł liczby w tradycyjny sposób omówiony powyżej. Jeśli pierwszy bit znaku jest równy <math>0</math>, to liczba jest nieujemna, a jeśli <math>1</math>, to jest niedodatnia. 

Oto tabela 16 liczb 4-bitowych zakodowanych tą metodą:
<table CELLPADDING=6 border=1 align=center>
<tr>
<td>bity</td>
<td>wartość</td>
</tr>
<tr>
<td align=right>0000<br>0001<br>0010<br>0011<br>0100<br>0101<br>0110<br>0111<br>1000<br>1001<br>1010<br>1011<br>1100<br>1101<br>1110<br>1111</td>
<td align=right>0<br>1<br>2<br>3<br>4<br>5<br>6<br>7<br>-0<br>-1<br>-2<br>-3<br>-4<br>-5<br>-6<br>-7</td>
</tr></table>
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 <math>0\neq-0</math>, o co bardzo łatwo porównując tradycyjnie bit po bicie zawartości bitowe takich reprezentacji.

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

===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 <math>n-1</math> bitów reprezentuje negatyw modułu liczby. Podobnie, jak poprzednio, jeśli pierwszy bit znaku jest równy <math>0</math>, to liczba jest nieujemna, a jeśli <math>1</math>, to jest niedodatnia. 

Oto tabela 16 liczb 4-bitowych zakodowanych tą metodą w kodzie znak – moduł odwrotny:
<table CELLPADDING=6 border=1 align=center>
<tr>
<td>bity</td>
<td>wartość</td>
</tr>
<tr>
<td align=right>0000<br>0001<br>0010<br>0011<br>0100<br>0101<br>0110<br>0111<br>1000<br>1001<br>1010<br>1011<br>1100<br>1101<br>1110<br>1111</td>
<td align=right>0<br>1<br>2<br>3<br>4<br>5<br>6<br>7<br>-7<br>-6<br>-5<br>-4<br>-3<br>-2<br>-1<br>-0</td>
</tr></table>
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 <math>n</math>-bitowych mamy ten sam zakres <math>-2^{n-1}+1\ldots 2^{n-1}-1</math> i różnych liczb reprezentowanych jest w związku z tym <math>2^n-1</math>. 

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 <math>-4</math> do <math>6</math>. Otrzymamy
      1011
      0110
      -- ---
 (1)  0001
i teraz jedynkę przeniesienia <math>(1)</math> 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 <math>n</math>-bitowej reprezentacji traktujemy jako <math>-2^{n-1}</math>, a pozostałe tradycyjnie jako wartości, kolejno <math>2^{n-2},\ldots,2^0</math>. Popatrzmy, jak wygląda nasza tabela czterobitowych wartości zapisanych w kodzie uzupełnieniowym. Kolejno od lewej bity nają wartości <math>-8,4,2,1</math>.Z trzech młodszych bitów generujemy wszystkie wartości od 0 do 7, a jeśli włączymy bit <math>-8</math>, to dodanie do niego tych wartości da nam liczby od <math>-8</math> do <math>-1</math>. 

<table CELLPADDING=6 border=1 align=center>
<tr>
<td>bity</td>
<td>wartość</td>
</tr>
<tr>
<td align=right>0000<br>0001<br>0010<br>0011<br>0100<br>0101<br>0110<br>0111<br>1000<br>1001<br>1010<br>1011<br>1100<br>1101<br>1110<br>1111</td>
<td align=right>0<br>1<br>2<br>3<br>4<br>5<br>6<br>7<br>-8<br>-7<br>-6<br>-5<br>-4<br>-3<br>-2<br>-1</td>
</tr></table>
Kod uzupełnieniowy

W n-bitowym kodzie uzupełnieniowym mamy następujące własności:
*Wartości są z przedziału <math>[-2^{n-1},2^{n-1}-1]</math>
*Każda wartość jest reprezentowana jednoznacznie
*Liczb ujemnych jest o jeden więcej niż dodatnich
*<math>000\ldots 0</math> to zawsze <math>0</math>, a <math>111\ldots 1</math> to zawsze <math>-1</math>

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ć <math>-4</math> do <math>6</math>, 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||uwaga_1|
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ć <math>4</math> do <math>6</math>. 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 <math>0111\ldots 1</math> daje nam najmniejszą liczbę ujemną, czyli <math>1000\ldots 0</math>, 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 <math>0,99999999</math>. Błąd się wziął stąd, że w zestawie wartości reprezentowanych przez kalkulator brakuje jednej trzeciej. Zamiast niej mamy jej przybliżenie <math>0,33333333</math>, które pomnożone przez <math>3</math> 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 <math>\frac{1}{2},\frac{1}{4},\frac{1}{8},\ldots</math>. Liczba <math>\frac{1}{2}</math> będzie zatem miała przedstawienie <math>0.1</math>, liczba <math>\frac{1}{4}</math> będzie miała przedstawienie <math>0.01</math>, liczba <math>\frac{3}{4}</math> będzie miała przedstawienie <math>0.11</math> 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 <math>\frac{5}{16}</math> ma przedstawienie <math>0.0101</math>: jest to po prostu <math>5</math> czyli <math>101</math> 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ą <math>5</math> i <math>2</math>, 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 <math>u</math> w binarnym systemie pozycyjnym.
 Założenie: <math>0\le u <1</math>.
 Napisz <math>0</math>.. Kolejne cyfry rozwinięcia binarnego będziemy generować w następujący sposób:
 Dopóki otrzymujesz nienapotkane wcześniej wartości <math>u</math> wykonuj
 1. Pomnóż <math>u</math> przez 2
 2. Jeżeli otrzymana wartość jest mniejsza od 1, to dopisz cyfrę <math>0</math>
 3. Jeżeli otrzymana wartość jest równa co najmniej 1, dopisz cyfrę  <math>1</math> i odejmij od 
    wyniku 1. Z chwilą, gdy powtórzy się wartość <math>u</math>, zakończ procedurę; wypisany ciąg 
    jest okresowy, a jego okresem jest ciąg bitów między powtórzeniami.  


<table CELLPADDING=6 border=1 align=center> <tr><td>bity</td><td>wartość</td></tr><tr><td>0.<br>0<br>1<br>0<br>0</td>
<td><math>\frac{2}{7}</math><br><math>\frac{4}{7}</math><br><math>\frac{1}{7}</math><br><math>\frac{2}{7}</math><br><math>\frac{4}{7}</math></td>
</tr></table>

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


Widzimy, że <math>\frac{2}{7}</math> ma rozwinięcie binarne <math>0.010010010\ldots</math>. Okresem jest <math>(010)</math>. 

Spróbujmy znaleźć jeszcze rozwinięcie binarne dla <math>\frac{1}{10}</math>.

<table CELLPADDING=6 border=1 align=center>
<tr>
<td>bity</td>
<td>wartość</td>
</tr>
<tr>
<td align=center>0.<br>0<br>0<br>0<br>1<br>1</td>
<td align=center><math>\frac{1}{10}</math><br><math>\frac{2}{10}</math><br><math>\frac{4}{10}</math><br><math>\frac{8}{10}</math><br><math>\frac{6}{10}</math><br><math>\frac{2}{10}</math></td>
</tr></table>
Binarne rozwinięcie <math>\frac{1}{10}=0.0(0011)</math>

Zauważmy jeden wstrząsający fakt: nawet tak prosta liczba jak <math>\frac{1}{10}</math> ma nieskończone binarne rozwinięcie okresowe. Oczywiście takie rozwinięcia mają także <math>\frac{2}{10},\frac{3}{10},\frac{4}{10}\frac{6}{10}\frac{7}{10},\frac{8}{10}\frac{9}{10}</math>. I rzeczywiście, gdy chcemy w komputerze (a nawet w kalkulatorach) reprezentować <math>\frac{1}{10}</math>, 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 <math>k</math>-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 <math>k</math>-tym miejscu przybliżenia (zaokrąglenie w górę). Oto kolejne przybliżenia <math>\frac{1}{10}</math> w zależności od stopnia dokładności, czyli określenia, ile cyfr po kropce binarnej chcemy mieć. 

<table CELLPADDING=6 border=1 align=center>
<tr>
<td>Numer bitu zaokrąglenia</td>
<td>reprezentacja</td>
</tr>
<tr>
<td align=right>1<br>2<br>3<br>4<br>5<br>6<br>7<br>8<br>9<br>...</td>
<td align=left>0.0<br>0.00<br>0.001<br>0.0010<br>0.00011<br>0.000110<br>0.0001101<br>0.00011010<br>0.000110011<br>&nbsp;</td>
</tr></table>
Kolejne zaokrąglenia <math>\frac{1}{10}</math>

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 <math>\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}</math>. Nie ma liczników, które przy tych mianownikach lepiej przybliżałyby <math>\frac{1}{10}</math>.

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 <math>10^{-34}</math>. Astrofizycy z kolei używają wielkości astronomicznych; promień Wszechświata choćby to jest wielkość rzędu <math>10^{23}m</math>. 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  <math>40000</math> 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 <math>-2^{k-1}</math> a <math>2^{k-1}-2^{-u}</math> i wartości w nim reprezentowane są równomiernie rozłożone co <math>2^{-u}</math>. 
}}

==System zmiennopozycyjny==
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: <math>h=0,000000000000000000000000000000000663 Js</math>. Gdyby podręczniki mechaniki kwantowej zawierały tak zapisywane wielkości kwantowe, byłyby nieczytelne. Zamiast takiego zapisu stosuje się znacznie poręczniejszy: <math>6,63 \cdot 10^{-34} Js</math>. 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ę <math>\frac{3}{8}</math> można przedstawić jako 
<center><math>\frac{3}{8}\cdot 2^0 = \frac{3}{4}\cdot 2^{-1} = \frac{3}{2}\cdot 2^{-2}= 3\cdot 2^{-3} =  \ldots</math></center>
i podobnie w drugą stronę: 
<center><math>\frac{3}{8}= \frac{3}{16}\cdot 2^{1} = \frac{3}{32}\cdot 2^{2}=  \ldots</math>.</center>
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 <math>[\frac{1}{2},1)</math> dla wartości dodatnich oraz <math>[-1,-\frac{1}{2})</math> 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 <math>(m,c)</math>, gdzie <math>m\in[-1,-\frac{1}{2})\cup[\frac{1}{2},1)</math> jest mantysą, 
 zaś <math>c</math>, nazywane cechą, określa o ile pozycji w prawo (dla <math>c</math> ujemnych) bądź w lewo (dla <math>c</math> dodatnich) 
 należy przesunąć mantysę,  aby uzyskać żądaną wartość. Interpretacja takiej reprezentacji wyraża się wzorem 
                                   <math>x=m2^c</math>

==System o 3 bitach cechy i 4 mantysy==
Pozostaje nam zatem umówić się, ile bitów przeznaczymy na mantysę, a ile na cechę. Typowe wartości to <math>(m=52, c=12)</math>, <math>(m=40,c=8)</math>. Dla celów ilustracyjnych przyjmijmy, że <math>(m=4, c=3)</math> 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 <math>64</math> różnych liczb niezerowych. 

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

Spróbujmy znaleźć reprezentację liczby <math>\frac{2}{11}</math>. 
Zaczynamy od zamiany tej liczby na system binarny, otrzymując kolejno bity <math>0.001011\ldots</math>. Tu możemy już przerwać, mimo że jeszcze nie trafiliśmy okresu, gdyż i tak interesują nas tylko <math>3</math> 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 <math>3</math> znaczących cyfr, dostajemy liczbę <math>0.00110</math>, czyli <math>\frac{3}{16}</math>. Normalizujemy ją przesuwając o 2 pozycje w lewo, czyli mnożymy przez <math>2^2</math>, więc ostatecznie dostajemy <math>110 \ \ 0110</math>. Cecha jest oczywiście równa <math>-2</math> - niweluje efekt przesunięcia o 2 pozycje. Zatem liczba <math>\frac{3}{16}=2^{-2}\cdot \frac{3}{4}</math> najlepiej przybliża <math>\frac{2}{11}</math> 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 

<center><math>\frac{|\frac{2}{11}-\frac{3}{16}|}{\frac{2}{11}}=\frac{1}{32}</math>.</center> 

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

<table CELLPADDING=6 border=1 align=center>
<tr>
<td>cecha</td>
<td>mantysa</td>
<td>wartość</td>
</tr>
<tr>
<td align=center>000<br>000<br>000<br>000</td>
<td align=center>0100<br>0101<br>0110<br>0111</td>
<td align=center><math>\frac{4}{8}</math><br><math>\frac{5}{8}</math><br><math>\frac{6}{8}</math><br><math>\frac{7}{8}</math></td>
</tr></table> 

Dla cechy <math>1</math> wartości te mnożą się przez 2:

<table CELLPADDING=6 border=1 align=center>
<tr>
<td>cecha</td>
<td>mantysa</td>
<td>wartość</td>
</tr>
<tr>
<td align=center>001<br>001<br>001<br>001</td>
<td align=center>0100<br>0101<br>0110<br>0111</td>
<td align=center><math>\frac{4}{4}</math><br><math>\frac{5}{4}</math><br><math>\frac{6}{4}</math><br><math>\frac{7}{4}</math></td>
</tr></table> 

... i dalej dla cech 2 i 3: 
<table align=center><tr><td>
<table CELLPADDING=6 border=1 align=center>
<tr>
<td>cecha</td>
<td>mantysa</td>
<td>wartość</td>
</tr>
<tr>
<td align=center>010<br>010<br>010<br>010</td>
<td align=center>0100<br>0101<br>0110<br>0111</td>
<td align=center><math>\frac{4}{2}</math><br><math>\frac{5}{2}</math><br><math>\frac{6}{2}</math><br><math>\frac{7}{2}</math></td>
</tr></table></td><td>&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td>
<table CELLPADDING=6 border=1 align=center>
<tr>
<td>cecha</td>
<td>mantysa</td>
<td>wartość</td>
</tr>
<tr>
<td align=center>011<br>011<br>011<br>011</td>
<td align=center>0100<br>0101<br>0110<br>0111</td>
<td align=center><math>\frac{4}{1}</math><br><math>\frac{5}{1}</math><br><math>\frac{6}{1}</math><br><math>\frac{7}{1}</math></td>
</tr></table></td></tr></table>

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

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><div class="mw-collapsible-content" style="display:none">
dla cech równych -1 i -2:
<table align=center><tr><td>
<table CELLPADDING=6 border=1 align=center>
<tr>
<td>cecha</td>
<td>mantysa</td>
<td>wartość</td>
</tr>
<tr>
<td align=center>111<br>111<br>111<br>111</td>
<td align=center>0100<br>0101<br>0110<br>0111</td>
<td align=center><math>\frac{4}{16}</math><br><math>\frac{5}{16}</math><br><math>\frac{6}{16}</math><br><math>\frac{7}{16}</math></td>
</tr></table></td><td>&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td>
<table CELLPADDING=6 border=1 align=center>
<tr>
<td>cecha</td>
<td>mantysa</td>
<td>wartość</td>
</tr>
<tr>
<td align=center>110<br>110<br>110<br>110</td>
<td align=center>0100<br>0101<br>0110<br>0111</td>
<td align=center><math>\frac{4}{32}</math><br><math>\frac{5}{32}</math><br><math>\frac{6}{32}</math><br><math>\frac{7}{32}</math></td>
</tr></table></td></tr></table>

oraz dla cech równych -3 i -4:
<table align=center><tr><td>
<table CELLPADDING=6 border=1 align=center>
<tr>
<td>cecha</td>
<td>mantysa</td>
<td>wartość</td>
</tr>
<tr>
<td align=center>101<br>101<br>101<br>101</td>
<td align=center>0100<br>0101<br>0110<br>0111</td>
<td align=center><math>\frac{4}{64}</math><br><math>\frac{5}{64}</math><br><math>\frac{6}{64}</math><br><math>\frac{7}{64}</math></td>
</tr></table></td><td>&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td>
<table CELLPADDING=6 border=1 align=center>
<tr>
<td>cecha</td>
<td>mantysa</td>
<td>wartość</td>
</tr>
<tr>
<td align=center>100<br>100<br>100<br>100</td>
<td align=center>0100<br>0101<br>0110<br>0111</td>
<td align=center><math>\frac{4}{128}</math><br><math>\frac{5}{128}</math><br><math>\frac{6}{128}</math><br><math>\frac{7}{128}</math></td>
</tr></table></td></tr></table>
</div></div>

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

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 <math>-8</math> i kolejne wartości to <math>-7,-6,-5,-\frac{8}{2},-\frac{7}{2},-\frac{6}{2}\ldots</math>.

==Zero==
Pozostała sprawa zera. Nie da się zera przedstawić w podanej postaci, gdyż żadna z liczb <math>m2^c</math> zerem być nie może dla mantys co do modułu większych od 1/2. Najczęściej stosowane rozwiązanie polega na tym, że wyłącza się jedną z cech (najmniejszą) i ustala, że jeśli liczba ma tę cechę, to jest równa zero niezależnie od mantysy. W naszym systemie więc przyjęcie tego rozwiązania prowadziłoby do wyłączenia grupy 8 liczb o cesze -4 z naszego repertuaru. Tu jest to dużo, ale w przypadku cech większych ta strata jest niezauważalna. 

==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==
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. 

{{przyklad| 1||
Zacznijmy od dodania <math>\frac{3}{32}+\frac{3}{32}</math>. Każda z tych liczb ma zapis <math>101 \ \ 0110</math>. Cechy są równe, więc nie potrzeba niczego denormalizować. Wykonujemy dodawanie mantys otrzymując <math>1100</math>. 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 <math>110 \ \ 0110</math>, czyli <math>\frac{3}{16}</math>. Zauważmy przy okazji, że mnożenie przez 2 i dzielenie przez 2 można wykonywać bezpośrednio dodając lub odpowiednio odejmując jedynkę od cechy!}}

{{przyklad| 2||
Dodajmy teraz <math>\frac{3}{8}</math> do <math>\frac{5}{2}</math>. Reprezentacje bitowe w naszym systemie tych dwóch wartości to odpowiednio <math>111 \ \ 0110</math> (czyli <math>2^{-1}\cdot \frac{3}{4}</math>) oraz <math>010 \ \ 0101</math> (czyli <math>2^{2}\cdot \frac{5}{8}</math>). Różnica w cechach to 3, więc o tyle bitów w prawo trzeba przesunąć mantysę <math>\frac{3}{16}</math>, 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: <math>0101</math> oraz <math>0000110</math>. Wynikiem jest nieco przydługa mantysa <math>0101110</math>, 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 <math>010 \ \ 0110</math>. Cecha bez zmian, a mantysa wskutek zaokrąglenia została nieco powiększona. Ostatecznie zatem uzyskaliśmy <math>3</math>, która to liczba najlepiej przybliża u nas dokładny wynik, czyli <math>\frac{23}{8}</math>. Alternatywą było <math>\frac{5}{2}</math>, położone nieco dalej.}} 

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


 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 <math>\frac{5}{2}+\frac{3}{16}+\frac{3}{16}</math>, to w przypadku, gdy zaczniemy wykonywać działania od lewej strony, dostaniemy zarówno po pierwszym, jak i po drugim dodawaniu  <math>\frac{5}{2}</math>, ale gdy dodamy najpierw dwie mniejsze liczby <math>\frac{3}{16}+\frac{3}{16}</math>, a potem wynik tego dodawania <math>\frac{3}{8}</math> do <math>\frac{5}{2}</math>, dostaniemy <math>3</math>, tak jak w przykładzie pierwszym. Oznacza to, że 


 DODAWANIE ZMIENNOPOZYCYJNE NIE JEST ŁĄCZNE!


{{cwiczenie|||
Który z uzyskanych wyników jest bliższy prawdziwemu?}}


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Odpowiedź</span>
<div class="mw-collapsible-content" style="display:none">
3</div></div>


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 wiadomo ile ich było, mogą pozostać niezauważone przez większe. 

{{cwiczenie|||
Zaprojektuj algorytm optymalnego dodawania <math>n</math> argumentów. }}


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Odpowiedź</span>
<div class="mw-collapsible-content" style="display:none">
Posortuj dane od liczby najmniejszej do największej względem modułów i dopóki są choć dwa argumenty wykonuj następujące działanie: pobierz z posortowanego zbioru dwie najmniejsze wartości, dodaj je do siebie i włóż do zbioru z powrotem wynik dodawania. Problemem, i to niebanalnym, jest szybka realizacja tego algorytmu, w szczególności poradzenie sobie z problemem wstawiania z powrotem częściowych wyników. Powrócimy do tego problemu w wykładzie o kolejkach na Metodach programowania. 
W każdym razie można zaprojektować rozwiązanie, które od chwili posortowania modułów będzie działało w czasie linowym. </div></div>


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. 


 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ń.