Arytmetyka z Nasyceniem

Wstęp

Dodawanie dwóch liczb w komputerze jest bardzo wygodne, ale problem pojawa się, gdy wynik nie mieści się w zakresie zmiennej. Wtedy nie można mieć pewności co do wyniku, ponieważ jednostka arytmetyczna ucina część wyniku. Rozwiązaniem jest napisanie własnych funkcji tak, aby wynik nigdy nie wyszedł poza zakres. W tym artykule zostanie wyjaśnione jak takie funkcje można napisać.

Problem

Przed przystąpieniem do pisania funkcji warto zastanowić się skąd i na czym polega problem. Komputerowa jednostka arytmetyczna ALU ma pewne zdefiniowane zasady dodawania. Dodawanie liczb jest bardzo proste. Poczynając od najmniej znaczącego bitu dodawj dwa bity. Jeśli wynik nie mieści się na jednym bicie to mniej znaczący bit pozostaw, a drugi dodaj do następnej pary bitów. Innymi słowy to dodawanie pisemne, ale w systemie binarnym. Przykładowo dodając dwie 8 bitowe liczby bez znaku:

Wiedząc już jak wygląda dodawanie zastanówmy się nad następującym przypadkiem:

Jak można zauważyć wynik wymaga 9 bitów, a zmienne są jedynie 8 bitowe. W tym momencie jednostka arytmetyczna ucina nadmiarowy bit i zapisuje jedynie pierwsz 8 obliczonych bitów do zmiennej. W rezultacie nietrudno się domyśleć, że wynik nie będzie poprawny. W tym przypadku według komputera 39 + 85 = 167 + 213 co oczywiście nie jest prawdą! Z tego powodu stosuje się często nasycenie.

Dodawanie z nasyceniem rozwiązuje częściowo problem z nieprawidłowym wynikiem. Otóż jeśli wynik wykracza poza zakres pojemności zmiennej to jest zwracana odpowiednio wartość najmniejsza lub największa zakresu. W podanym wyżej przykładzie zamiast uzyskania wartości 124 wynik zostałby ustawiony na 255 czyli największą wartość do zapisu na 8 bitach.

Implementacja

Liczby bez znaku

Dodawanie

Dodawanie dwóch liczb bez znaku może spowodować jedynie nadmiar (ang. overflow). Można się przed tym ustrzec sprawdzając czy różnica pomiędzy maksymalną wartością, a a jest w stanie znaleźć b. Jeśli nie to należy zwróci maksymalny zakres, a jeśli tak to po prostu zwrócić sumę.

1. def dodaj_u32(a, b):
2.   if (uint.MaxValue - a <= b):
3.     return uint.MaxValue
4.   else:
5.     return a + b

Odejmowanie

Dla liczb bez znaku najmniejszą wartością jest 0. Jeśli b będzie większa od a to dojdzie do przekroczenia dolnego zakresu (ang. underflow). W takim jednak przypadku wystarczy zwrócić 0, aby uniknąć problemu.

1. def odejmij_u32(a, b):
2.   if (a >= b):
3.     return a - b
4.   else:
5.     return 0

Liczby z znakiem

Dodawanie

Dodawanie dwóch liczb ze znakiem wymaga sprawdzenia wielu różnych przypadków. Otóż jeśli obydwie liczby są dodatnie to może dojść do przepełnienia (overflow), więc dla tego przypadku należy postępować jak dla liczb bez znaku. Drugim przypadkiem jest sytuacja, gdy liczby są różnego znaku - wtedy wystarczy zwrócić ich sumę. Ostatni przypadek dotyczy sytuacji, gdy obie liczby są ujemne. Wtedy należy postępować podobnie jak w przypadku dwóch liczb dodatnich, ale pamiętać, że zakres maksymalny jest inny (np. w systemie U2. jest jedna liczba ujemna więcej).

1. def dodaj_i32(a, b):
2.   if (a >= 0 and b >= 0):
3.     return a + b if (int.MaxValue - a >= b) else int.MaxValue
4.   if (a < 0 and b < 0):
5.     return int.MinValue if (Math.Abs(int.MinValue - a) >= Math.Abs(b)) else a + b
6.   return a + b

Odejmowanie

Jak wiadomo odejmowanie można zastąpić poprzez dodawanie jeśli drugi argument ustawi się na liczbę przeciwną. Jednak i tu czai się pewien drobny problem. Otóż wartość absolutna minimalnej wartości zakresu zmiennej nie ma dodatniego odpowiednika. Z tego powodu należy dopisać własną implementację wartości absolutnej, która odpowiednio będzie zmieniać wartość na przeciwną w określonym zakresie. Oto przykładowa implementacja:

1. def modul_i32(a):
2.   if (a == int.MinValue):
3.     return int.MaxValue
4.   return -a

Wtedy można przejść do napisania funkcji odejmij():

1. def odejmij_i32(a, b):
2.   return dodaj_i32(a, modul(b))

Testowanie funkcji

Dla każdej funkcji należy napisać oddzielne testy. W każdym przypadku należy pamiętać, aby sprawdzić skrajne przypadki. Oto przykładowe testy do funkcji dodaj() dla liczb bez znaku.

1. assert(dodaj_u32(2, 3) == 5)
2. assert(dodaj_u32(2, uint.MaxValue) == uint.MaxValue)
3. assert(dodaj_u32(2, uint.MaxValue - 3) == uint.MaxValue - 1)
4. print("Funkcja poprawna!")

• Kod źródłowy Implementacja