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 nadmiar3 ani niedomiar4.
Niech \(a={\mathop{\mathrm{rd}}}(a)=2^{c_a}m_a\) i \(b={\mathop{\mathrm{rd}}}(b)=2^{c_b}m_b\) będą argumentami. Przyjmijmy, że a ≥ b > 0. Ich (dokładna) suma wynosi:
a + b = 2ca(maa + mb2 − (ca − cb)) = 2cams
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 wprowadziła „obowiązek” korzystania z dodatkowego bitu.
Jeżeli symbolem \({\mathop{\mathrm{fl}}}\) oznaczać będziemy realizację działania w arytmetyce zmiennoprzecinkowej, to:
$${\mathop{\mathrm{fl}}}(a+b)={\mathop{\mathrm{rd}}}(a+b)$$
Ogólnie, dla dowolnej operacji ⋄
$${\mathop{\mathrm{fl}}}(a \diamond b) = {\mathop{\mathrm{rd}}}(a\diamond b)= (a \diamond b)(1+\varepsilon),\quad \varepsilon=\varepsilon(a,b,\diamond), \quad |\varepsilon|\le 2^{-t}$$
uzyskany (komputerowo) wynik, nieznacznie, różni się od wyniku „prawdziwego”.
Wydaje się, że niewielkie (2 − t ∈ [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:
- A1(a2 − b2) = a2 − b2
- A2(a2 − b2) = (a − b)(a + b)
$$\begin{split} {\mathop{\mathrm{fl}}}(a^2-b^2) & = (a \times a(1+\varepsilon_1)-b\times b(1+\varepsilon_2))(1+\varepsilon_3)\\ & = (a^2-b^2) \left(1+\frac{a^2\varepsilon1 -b^2\varepsilon_2}{a^2-b^2}\right)(1+\varepsilon3)\\ & = (a^2-b^2)(1+\delta) \end{split}$$
W przypadku gdy a2 jest bliskie b2, a ε1 i ε2 mają przeciwne znaki — błąd względny δ moze być dowolnie duży.
W przypadku drugiego algorytmu:
$$\begin{split} {\mathop{\mathrm{fl}}}((a-b)(a+b)) & = ((a-b)(1+\varepsilon_1)(a+b)(1+\varepsilon_2))(1+\varepsilon_3)\\ & = (a^2-b^2)(1+\delta) \end{split}$$
gdzie δ ≤ |ε1| + |ε2| + |ε3|, zatem δ jest zawsze mniejszy od 3 ⋅ 2 − t.
W szczególności, ze względu na algorytm dodawania ([eq:suma]) gdy a i b są takie, że \(|b|\le \frac{1}{2}2^{-t}|a|\), zachodzi zależność:
$${\mathop{\mathrm{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ą.