10
Saturation [w C++]
Większość języków programowania posiada pewne (standardowe dla siebie) typy danych. To właśnie zmienne z konkretnym typem danym przechowują pewną wartość. Typ danych określa jak wielką (bądź jak małą) liczbę dana zmienna może zapamiętać. Weźmy chyba najpopularniejszy typ integer (int), który w jęzku C++ przyjmuje liczby całkowite z przedziału <−2147483648, 2147483647>. Tym samym, każdy typ danych ma określony dla siebie z góry przedział liczb, które może przyjmować. Zastanówmy się (na przykładzie języka C++) co stanie się, gdy programista będzie próbował przekroczyć te limity.
Wykonajmy prosty eksperyment na dwóch liczbach typu integer (int). Weźmy dwie liczby (int a, int b) i umieśćmy w nich takie wartości, które mieszą się w przedziale <−2147483648, 2147483647>, jednak, których suma przekracza dany przedział, np.: a=2147483647 b=1.
Wynikiem tego działania (wg komputera) jest liczba -2147483648. Dzieje się tak dlatego, że po przekroczeniu zakresu, komputer zaczyna liczyć od początku (tj. przeciwnego, skrajnego elementu przedziału). Wykonana przez nas operacja nazywana jest potocznie dodawaniem „z zawijaniem” (wrap around). Umówmy się, że jeśli podczas dodawania suma wyjdzie poza zakres i rozpocznie się „liczenie” od początku przedziału, nazwiemy to „przekręceniem” licznika. Zastanówmy się nad wadami takiego dodawania. Jeśli nasz program przyjmie dane, których suma nie mieści się w zakresie danego typu, a my wykonamy na nich operację dodawania, otrzymamy błędny wynik. Co gorsze, możemy nawet nie zauważyć, że otrzymaliśmy zły wynik (zwłaszcza, jeśli takie dodawanie to tylko jeden element z szeregu długiej listy innych działań). Z pomocą przychodzą nam tutaj tzw. operacje „z nasyceniem” (saturation). Jeśli suma dwóch liczb przekroczy ustalony zakres, jako wynik zwrócona zostanie wartość maksymalna (lub minimalna) tego zakresu. Programując w asemblerze, o tym, czy chcemy posługiwać się arytmetyką z nasyceniem czy też z zawijaniem, możemy zdecydować bawiąc się flagą CF (carry flag), lub też (bez wnikania w szczegóły), użyć instrukcji takich jak PAADW bądź PADDSW (pierwsza z mnemonik odpowiada za dodawanie z zawijaniem, druga – z nasyceniem). My jednak zajmiemy się tą problematyką używając języka C++ (bez wstawek asemblerowych).
Napiszemy prostą funkcje (a właściwie szablon), który odpowiada za wykonanie dodawania z nasyceniem. Tak wygląda kod, a poniżej znajduje się jego omówienie.
#include <iostream> using namespace std; template<typename T> T add(T a, T b, T c=0) { enum flags {minus=-1, plus=1}; flags flag=plus; if(a<0 && b<0) { a*=-1; b*=-1; flag=minus; } T sum = a+b; bool OK=1; if ((a>=0 && b<=0) || (b>=0 && a<=0)) OK=0; if ( OK &&((sum<a) || (sum<b)) ) return c; else return sum*flag; } int main() { int a, b, c; cin >> a >> b; cout << add(a,b); return 0; } |
Dla lepszej czytelności skorzystajmy z oznaczeń: a, b to dwie zmienne typu T. Za <-t, t> będziemy uważać zakres typu T (każda zmienna typu T należy do przedziału <-t, t>
Funkcja addS() odpowiadać będzie za dodawanie z nasyceniem. Znak ‘+’ oznaczać będzie dodawanie z zawijaniem (czyli domyślnie dostępne w języku C++). addS() przyjmuje trzy argumenty, pierwsze dwa to składniki (je będziemy dodawać), natomiast trzeci argument określa co zwróci nasza funkcja, gdy suma dwóch pierwszych argumentów wyjdzie poza zakres typu T.
Dodatkowo a, b ∈ <-t, t>
s=a+b
Posłużymy się następującym lemat:
(a ≥ 0 ^ b ≤ 0) ∨ (a ≤ 0 ^ b ≥ 0) ⇒ a+b ∈ <-t, t> (jeśli a i b są różnych znaków, to s=a+b będzie zawsze mieściło się w przedziale <-t, t>).
Dzięki temu wyeliminowaliśmy przypadek, w którym wyjście za zakres zmiennej nigdy nie zastąpi. W takim razie kiedy wrap around następuje? Odpowiedź jest prosta, wtedy, gdy dodawane liczby są tych samych znaków. Zajmijmy się na razie liczbami nieujemnymi: (a ≥ 0 ^ b ≥ 0).
Zauważmy, że gdy wyjście poza zakres nie występuje to suma liczb (a+b) jest zawsze większa od składników (a, b). Stąd jeśli ((a+b) ≥ a) ^ ((a+b) ≥ b ) to jako wynik powinniśmy zwrócić sumę a+b (gdyż „przekręcenie” licznika nie nastąpiło, suma liczb poza przedział ustalony przez typ nie wyszła).
W takim razie, jeśli widzimy, że a>a+b lub b>a+b , to mamy pewność, że „przekręcenie” licznika tym razem nastąpiło.
Rozważmy pesymistyczny przypadek: a,b ∈ <-t, t> oraz a=b=t [bo, aby uzyskać możliwie największą liczbę] po przekręceniu licznika, musimy zsumować możliwie największe liczby]. Stąd wynik operacji z zawijaniem to a+b=t+t=2t=-1, zmniejszając któryś ze składników (oczywiście tak, aby nadal dodawanie „przekręcało licznik”) suma jest jeszcze mniejsza.
Tak więc nasz program powinien sprawdzać, czy suma jest większa od składników, jeśli jest, to wszystko OK. W przeciwnym wypadku, dodawanie wyszło poza zakres i nastąpiło przekręcenie licznika.
Przedstawiony sposób działa wyłącznie dla liczb nieujemnych. W takim razie co zrobić, jeśli chcemy dodać dwie liczby niedodatnie?
Zauważmy, że -|a|+(-|b|)=-||a|+|b||
Reasumując, wystarczy zmienić znak tych liczb (pomnożyć przez -1), zastosować warunek taki, jak dla liczb nieujemnych (bo przecież po przemnożeniu mamy już liczby nieujemne), a następnie otrzymany wynik przemnożyć ponownie przez -1 (przywracamy ujemny znak).
To tyle. Zapewne istnieje jeszcze wiele innych możliwości zakodowania operacji dodawania z nasyceniem. Ten sposób wydawał mi się jednak najprostszy i najbardziej intuicyjny, dlatego zdecydowałem się zaprezentować właśnie takie rozwiązanie problemu..