Arytmetyka zmiennopozycyjna

Problem z operacjami arytmetycznymi realizowanymi przez komputery polega na tym, że „po cichu" zakładamy, że argumenty równe są swoim reprezentacjom zmiennoprzecinkowym, oraz, że podczas obliczeń, nie wystąpi ani nadmiar¹ ani niedomiar².

Niech $a = rd (a) = 2^{c_{a}} m_{a}$ i $b = rd (b) = 2^{c_{b}} m_{b}$ będą argumentami. Przyjmijmy, że $a \geq b > 0$ . Ich (dokładna) suma wynosi:

a + b = 2^{c_{a}} (m a_{a} + m_{b} 2^{- (c_{a} - c_{b})}) = 2^{c_{a}} m_{s}

Mantysa wyniku wyliczana jest przez dodanie do mantysy liczby $a$ odpowiednio przekształconej (to znaczy tak, żeby cechy liczb $a$ i $b$ były jednakowe) mantysy liczby $b$ .

Wszystko to wygląda jakoś tak:

Jakość wyniku zależy od możliwości poprawnego zaokrąglenia wyniku. A zatem od liczby bitów, na których zapisywany jest wynik. Gdy jest ich tylko $t$ — nie jest dobrze. Historycznie, liczba dodatkowych bitów wewnętrznego rejestru arytmometru zmieniała się od zera aż do $t$ (wynikowy rejestr podwójnej długości). Dopiero norma IEEE-754 [1] wprowadziła „obowiązek" korzystania z dodatkowego bitu.

Jeżeli symbolem $fl$ oznaczać będziemy realizację działania w arytmetyce zmiennoprzecinkowej, to:

fl (a + b) = rd (a + b)

Ogólnie, dla dowolnej operacji $⋄$

fl (a ⋄ b) = rd (a ⋄ b) = (a ⋄ b) (1 + ε), ε = ε (a, b, ⋄), | ε | \leq 2^{- t}

uzyskany (komputerowo) wynik, nieznacznie, różni się od wyniku „prawdziwego".

Wydaje się, że niewielkie ( $2^{- t} \in [10^{- 15}, 10^{- 6}]$ ) względne błędy nie powinny mieć wielkiego wpływu na wyniki. Okazuje się, że jest inaczej, a sposób realizacji obliczeń może mieć ogromny wpływ na wyniki.

Rozpatrzmy dwa różne algorytmy wyliczania wartości różnicy kwadratów dwu liczb:

$A 1 (a^{2} - b^{2}) = a^{2} - b^{2}$
$A 2 (a^{2} - b^{2}) = (a - b) (a + b)$

\begin{aligned} fl (a^{2} - b^{2}) & = (a \times a (1 + ε_{1}) - b \times b (1 + ε_{2})) (1 + ε_{3}) \\ = (a^{2} - b^{2}) (1 + \frac{a^{2} ε 1 - b^{2} ε_{2}}{a^{2} - b^{2}}) (1 + ε 3) \\ = (a^{2} - b^{2}) (1 + δ) \end{aligned}

W przypadku gdy $a^{2}$ jest bliskie $b^{2}$ , a $ε_{1}$ i $ε_{2}$ mają przeciwne znaki — błąd względny $δ$ moze być dowolnie duży.

W przypadku drugiego algorytmu:

\begin{aligned} fl ((a - b) (a + b)) & = ((a - b) (1 + ε_{1}) (a + b) (1 + ε_{2})) (1 + ε_{3}) \\ = (a^{2} - b^{2}) (1 + δ) \end{aligned}

gdzie $δ \leq | ε_{1} | + | ε_{2} | + | ε_{3} |$ , zatem $δ$ jest zawsze mniejszy od $3 \cdot 2^{- t}$ .

W szczególności, ze względu na algorytm dodawania, gdy $a$ i $b$ są takie, że $| b | \leq \frac{1}{2} 2^{- t} | a |$ , zachodzi zależność:

$fl (a + b) \equiv a .$

(Wspominałam o tym na zajęciach z Technologii Informacyjnych.)

Konsekwencje tego mogą być bardzo poważne w przypadku numerycznego aproksymowania ilorazem różnicowym, pochodnej funkcji w punkcie. Zamiast otrzymywania coraz to lepszego przybliżenia pochodnej (gdy różnica wartości pomiędzy dwiema wartościami zmiennej niezależnej) dostaniemy wartości nie mające nic wspólnego z pochodną.

Cytowania

IEEE Standard for Floating-Point Arithmetic, IEEE, 2008. doi:10.1109/IEEESTD.2008.4610935

Nadmiar to sytuacja taka, gdy wynik operacji jest większy niż może być zapamiętany w formie komputerowej (całkowitej lub zmiennoprzecinkowej). ↩︎
Niedomiar występuje wtedy gdy wyniki jest mniejszy niż najmniejsza liczba jaką można w formie zmiennoprzecinkowej zapisać. ↩︎