R2_BB_Bledy.doc

(331 KB) Pobierz

MN03

Do arytmetyki zmiennoprzecinkowej

Przykład. Załóżmy, że wartości funkcji zostały obliczone na komputerze. Może się zdarzyć, że wykres funkcji ma mnóstwo różnych miejsc zerowych w okolicy , a sama funkcja nie jest gładka.

Tymczasem, ponieważ także , to funkcja ma dokładnie jedno miejsce zerowe (krotność pierwiastka – 4).

Wykonywanie realnych obliczeń na liczbach rzeczywistych w komputerze może być źródłem wielu innych zaskoczeń.

Przykład. W komputerze co można łatwo sprawdzić:

octave:7> 10 * (1.1 -1) - 1

ans = 8.8818e-16

Jaki wynik dostaniemy kalkulatorze?

Dlatego w praktyce numerycznej należy wystrzegać się testów w rodzaju

if (x == 1.0)

{

....

}

Źródło problemów leży w zbyt uproszczonym modelu obliczeniowym. Matematycznym modelem arytmetyki maszyny cyfrowej jest arytmetyka zmiennoprzecinkowa .

Niech będzie zadana liczba naturalna (jej znaczenie wyjaśni się dalej). Dowolną liczbę rzeczywistą można jednoznacznie przedstawić w postaci

gdzie jest znakiem, liczba całkowita cechą, a liczba rzeczywista mantysą liczby .

Zauważmy, że taki rozkład jest jednoznaczny i odpowiada przesuwaniu przecinka w rozwinięciu binarnym liczby do pierwszej cyfry znaczącej, tj. różnej od zera (stąd nazwa: reprezentacja zmiennoprzecinkowa (floating point)).

Mantysa ma w ogólności nieskończenie wiele cyfr binarnych w swoim rozwinięciu dwójkowym

W komputerach osobistych mamy do czynienia z reprezentacją liczb rzeczywistych, w której do zapisania liczby używa się ściśle określonej liczby bitów do zapisania mantysy i także określonej liczby bitów do zapisania cechy danej liczby niezerowej

Liczby zapisane przy użyciu powyższej sekwencji bitów nazywa się liczbami maszynowymi. Są to jedyne dokładnie zapisywalne w komputerze liczby rzeczywiste, pozostałe będą musiały zostać wyrażone z wykorzystaniem liczb maszynowych.

Reprezentacją zmiennoprzecinkową niezerowej liczby będziemy nazywać liczbę taką, że

gdzie jest liczbą dwójkową postaci , natomiast jest liczbą naturalną postaci .

Na znak liczby, , przeznaczony jest jeden bit. Wartości i dobiera się tak, żeby była tak bliska jak to możliwe. Stałą całkowitą dobiera się tak, by uzyskać zbalansowany zakres cechy (mniej więcej tyle samo wartości ujemnych i dodatnich), a zysk z korzystania z niej jest taki, że nie marnujemy dodatkowego bitu na przechowywanie znaku wykładnika potęgi dwójki .

Przy takim sposobie reprezentacji, jej błąd względny szacuje się przez

gdzie liczbę nazywa się precyzją arytmetyki. Precyzja arytmetyki zależy wyłącznie od liczby bitów przeznaczonych na reprezentację mantysy. Ostatnią nierówność wygodnie jest zapisać w równoważny sposób jako

Przykład. Rozważmy system, w którym zarówno na cechę, jak i mantysę, przeznaczone są jedynie po dwa bity, zatem jedna liczba maszynowa zajmuje 5 bitów. Ponieważ możliwy zakres wartości jest , to przyjmiemy korektę , dzięki czemu . Z kolei możliwe wartości mantysy to

$\displaystyle (1.00)_2 = 1,\qquad (1.01)_2 = 1.25,\qquad (1.10)_2 = 1.5,\qquad (1.11)_2 = 1.75.$

Wobec tego, jedyne (dodatnie) liczby maszynowe naszej pięciobitowej arytmetyki zmiennopozycyjnej to

$\displaystyle 0.500, 0.625, 0.750, 0.875 1.000 , 1.250, 1.500, 1.750 2.000, 2.500, 3.000, 3.500 4.000, 5.000, 6.000, 7.000$

Liczby maszynowe: reprezentowane dokładnie w pięciobitowej arytmetyce o precyzji $\displaystyle 2^{-2}$ . (Przedstawiliśmy tylko liczby nieujemne)

Standard IEEE 754. Z nielicznymi egzotycznymi wyjątkami (np. Cray C90), współczesne procesory implementują IEEE 754 Floating Point Standard, który definiuje dwa zasadnicze formaty reprezentacji zmiennoprzecinkowej liczb rzeczywistych:

Typ IEEE 754	Pojedynczej precyzji	Podwójnej precyzji
Nazwa typu w C	float	double
Liczba bitów cechy	8	11
Liczba bitów mantysy	23	52
Liczba bajtów dla typu w C	4	8
Bias (liczba powyżej)	127	1023
Orientacyjny zakres
Orientacyjna precyzja

Procesory Intel’a mają jedną z najlepszych implementacji standardu IEEE 754).

W Octave można łatwo podejrzeć reprezentację binarną liczby zmiennoprzecinkowej podwójnej precyzji (jest to domyślny typ numeryczny stosowany w MATLABie i Octave),

octave:9> format bit

octave:10> x = -2

x = 1100000000000000000000000000000000000000000000000000000000000000

octave:11> x = 1/4

x = 0011111111010000000000000000000000000000000000000000000000000000

octave:13> x = 0

x = 0000000000000000000000000000000000000000000000000000000000000000

octave:15> x = 0.1

x = 0011111110111001100110011001100110011001100110011001100110011010

(w MATLABie możemy zobaczyć tę samą liczbę w zapisie szestnastkowym).

Rozwinięcie dwójkowe liczby 0.1 jest nieskończone:

$\displaystyle 0.1 = (0.0001 1001 1001 1001 \ldots)_2.$

Ten banalny fakt jest bardzo często przeoczony przez programistów, a w 1991 roku doprowadził do awarii systemu antyrakietowego Patriot. Okazało się, że rakiety Patriot traciły skuteczność, gdy przez wiele godzin pozostawały w stanie gotowości. Jak zbadano, w celu pomiaru czasu, zliczano kolejne tyknięcia zegara rakiety, które następowały dokładnie co 0.1 sekundy. Następnie, w celu wyznaczenia prawdziwego czasu, mnożono liczbę tknięć zegara przez 0.1 (które właśnie było niedokładnie reprezentowane). Gdy cykli zegara było bardzo dużo, błąd bezwzględny wyznaczenia czasu stawał się na tyle poważny, że uniemożliwiał precyzyjne wyznaczenie parametrów toru lotu nieprzyjacielskiego obiektu.

Nie wszystkie maszyny liczące wykorzystują reprezentację dwójkową.

Nadmiar i niedomiar. W pierwszym przypadku liczba jest tak duża (co do modułu), że nie zawiera się w przedziale liczb reprezentowalnych, a w drugim jest tak mała, że musi być reprezentowana przez zero.

Np. próżnia wokół zera (na przykładzie 5-bitowej arytmetyki)

Arytmetyka IEEE 754 przyjmuje, że liczby dla których następuje overflow są reprezentowane przez specjalną wartość Inf (nieskończoność, ze znakiem), która propaguje się w obliczeniach zgodnie z powszechnie przyjętymi regułami, np. 1+Inf daje Inf, 1/Inf daje 0, Inf-Inf daje NaN, itd.

Np. wszystkie liczby większe od największej zapisywalnej liczby są reprezentowane przez Inf (na przykładzie 5-bitowej arytmetyki)

W dalszych rozważaniach zjawiska nadmiaru i niedomiaru będziemy dla uproszczenia zaniedbywać, jednak nie zawsze jest to uzasadnione, o czym niech świadczy poniższy przykład.

Przykład. Jedną z najczęściej wykonywanych operacji na wektorze $\displaystyle x = (x_1,\ldots,x_n)^T \in R^n$ jest obliczenie jego normy euklidesowej

$\displaystyle ||x||_2 = \sqrt{x_1^2 + \ldots x_n^2}.$

Jak widać, możemy tu łatwo zetknąć się ze zjawiskiem zarówno niedomiaru, jak i nadmiaru, gdyż może się na przykład tak złożyć, że mimo iż $\displaystyle ||x||_2$ jest reprezentowana, to $\displaystyle x_1^2$ już nie (np. w arytmetyce podwójnej precyzji $\displaystyle x_1 = 10^{200}$ i $\displaystyle x_2 = 1$ ). Łatwym wyjściem z tej sytuacji jest wstępna normalizacja danych tak, by wszystkie nie były większe od 1: niech $\displaystyle M = \max\{|x_i|: i = 1,\ldots,n\}$ i wtedy

$\displaystyle ||x||_2 = \sqrt{x_1^2 + \ldots x_n^2} = M\cdot\sqrt{\left(\frac{x_1}{M}\right)^2 + \ldots + \left(\frac{x_1}{M}\right)^2}.$

i teraz suma pod pierwiastkiem jest zawsze pomiędzy 1 a $\displaystyle N$ .

Liczby denormalizowane. Wymaganie, że mantysa jest postaci $\displaystyle 1+f$ , $\displaystyle f\geq 0$ , powoduje, że wokół zera pojawia się coś w rodzaju próżni. Formalnie, liczby mniejsze niż $\displaystyle 2^{1-1023}$ powinny być reprezentowane przez 0, lecz zazwyczaj zamiast tego

octave:16> format bit

octave:17> x = 2^(-1022)

x = 0000000000010000000000000000000000000000000000000000000000000000

...

Plik z chomika:

kinia04

Inne pliki z tego folderu: