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.
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 2 można wykonywać bezpośrednio dodając lub odpowiednio odejmując jedynkę od cechy!
Przykład 2
Dodajmy teraz \( \frac{3}{8} \) do \( \frac{5}{2} \). Reprezentacje bitowe w naszym systemie tych dwóch wartości to odpowiednio \( 111 \ \ 0110 \) (czyli \( 2^{-1}\cdot \frac{3}{4} \)) oraz \( 010 \ \ 0101 \) (czyli \( 2^{2}\cdot \frac{5}{8} \)). Różnica w cechach to 3, więc o tyle bitów w prawo trzeba przesunąć 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 nieco powiększona. Ostatecznie zatem uzyskaliśmy \( 3 \), która to liczba najlepiej przybliża u nas dokładny wynik, czyli \( \frac{23}{8} \). Alternatywą było \( \frac{5}{2} \), położone nieco dalej.
Przykład 3
Dodajmy teraz \( \frac{3}{16} \), czyli \( 110 \ \ 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 4, więc przesuwamy mantysę mniejszej liczby o 4 pozycje 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}{16} \) to za mały pikuś, żeby \( \frac{5}{2} \) 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 \( \frac{5}{2}+\frac{3}{16}+\frac{3}{16} \), 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}{16}+\frac{3}{16} \), a potem wynik tego dodawania \( \frac{3}{8} \) do \( \frac{5}{2} \), dostaniemy \( 3 \), tak jak w przykładzie pierwszym. Oznacza to, że
DODAWANIE ZMIENNOPOZYCYJNE NIE JEST ŁĄCZNE!
Ćwiczenie
Który z uzyskanych wyników jest bliższy prawdziwemu?
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.
Ćwiczenie
Zaprojektuj algorytm optymalnego dodawania \( n \) argumentów.
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.
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ń.