Najlepszy algorytm do unikania utraty precyzji?

Question

Niedawne zadanie domowe, które otrzymałem, prosi nas o wyrażenie, które może spowodować utratę precyzji podczas wykonywania w komputerze, i zmienić je tak, aby uniknąć tej straty.

Niestety, wskazówki dotyczące tego nie zostały jasno określone. Obserwując różne przykłady, wiem, że istnieją pewne metody, aby to zrobić: używając serii Taylora, używając koniugatów, jeśli zaangażowane są pierwiastki kwadratowe, lub znajdując wspólny mianownik, gdy odejmowane są dwie frakcje.

Mam jednak pewne problemy z zauważeniem, kiedy dokładnie nastąpi utrata precyzji. Do tej pory jedyne, co wiem na pewno, to to, że gdy odejmiesz dwie liczby, które są bliskie tego samego, utracisz precyzję, ponieważ wysokie cyfry są znaczące i tracisz je zaokrąglając.

Moje pytanie brzmi: jakie są inne typowe sytuacje, których powinienem szukać i jakie są uważane za "dobre" metody ich zbliżania się?

Na przykład, tutaj jest jeden problem:

f(x) = tan(x) − sin(x) when x ~ 0 

Jaki jest najlepszy i najgorszy algorytm do oceny to z tych trzech opcji:

(a) (1/ cos(x) − 1) sin(x), 
(b) (x^3)/2 
(c) tan(x)*(sin(x)^2)/(cos(x) + 1). 

Rozumiem, że gdy x jest blisko zero, tan (x) i sin (x) są prawie takie same. Nie rozumiem, jak i dlaczego któryś z tych algorytmów jest lepszy lub gorszy w rozwiązaniu problemu.

Answer 1

Zazwyczaj stosowana jest zazwyczaj następująca reguła: Dodając długą serię liczb, zacznij od liczb najbliższych od zera i kończ z największymi liczbami.

Wyjaśnienie, dlaczego to jest dobre, jest trudne. gdy dodajesz małe liczby do dużych liczb, istnieje szansa, że ​​zostaną całkowicie odrzucone, ponieważ są mniejsze niż najniższa cyfra w aktualnej mantysie dużej liczby. Weźmy na przykład taką sytuację:

a = 1,000,000; 
do 100,000,000 time: 
    a += 0.01; 

jeżeli jest mniejsza niż 0,01 najniższej cyfry mantysy, wówczas pętla nie robi nic, a końcowy wynik jest == 1000000 ale jeśli zrobisz to tak:

a = 0; 
do 100,000,000 time: 
    a += 0.01; 
a += 1,000,000; 

Niż mała liczba powoli rośnie, a prawdopodobieństwo znalezienia się w pobliżu wynosi około 2,000,000, co jest właściwą odpowiedzią.
To jest oczywiście ekstremalny przykład, ale mam nadzieję, że wpadniesz na ten pomysł.

Answer 2

Musiałem wziąć klasy liczbowej z powrotem, gdy byłem undergrad, i to było całkowicie bolesne. W każdym razie, IEEE 754 jest standardem zmiennoprzecinkowym zwykle implementowanym przez nowoczesne procesory. Warto zrozumieć jej podstawy, ponieważ daje to wiele intuicji odnośnie tego, czego nie robić. Uproszczonym wyjaśnieniem tego jest to, że komputery przechowują liczby zmiennoprzecinkowe w czymś podobnym do notacji naukowej o podstawie 2 z ustaloną liczbą cyfr (bitów) dla wykładnika i mantysy. Oznacza to, że im większa jest wartość bezwzględna liczby, tym mniej dokładnie można ją przedstawić. W przypadku 32-bitowych float w IEEE 754, połowa możliwych wzorów bitów reprezentuje od -1 do 1, mimo że liczby do około 10^38 są reprezentowalne za pomocą 32-bitowego float. Dla wartości większych niż 2^24 (około 16,7 miliona) 32-bitowe zmienne nie mogą dokładnie reprezentować wszystkich liczb całkowitych.

Co to oznacza dla Ciebie jest to, że na ogół chcą uniknąć następujące:

1. uwzględniając wartości pośrednie być duże, gdy oczekuje się, że ostateczna odpowiedź będzie niewielka.

2. Dodawanie/odejmowanie małych liczb do/z dużych liczb. Na przykład, jeśli napisał coś takiego:

   dla (wskaźnik pływaka = 17000000; indeksu < 17000001; index ++) {}

Pętla ta nigdy by zakończyć ponieważ posiadał 17.000.000 + 1 jest zaokrąglana w dół do 17,000,000. Jeśli miał coś takiego:

float foo = 10000000 - 10000000.0001 

Wartość foo będzie 0, nie -0,0001, ze względu na zaokrąglenia błąd.

Answer 3

Inną rzeczą, której należy unikać, jest odejmowanie liczb, które są prawie równe, ponieważ może to również prowadzić do zwiększenia wrażliwości na błąd zaokrągleń. Dla wartości zbliżonych do 0 cos (x) będzie bliskie 1, więc 1/cos (x) - 1 jest jednym z tych odejmowań, których chciałbyś uniknąć, jeśli to możliwe, więc chciałbym powiedzieć, że (a) należy unikać .

Answer 4

Moje pytanie brzmi, jakie są inne typowe sytuacje Byłbym patrząc dla i jakie są uważane za „dobre” metody ich zbliża?

Istnieje kilka sposobów na poważne lub nawet katastroficzne pogorszenie precyzji.

Najważniejszym powodem jest to, że liczby zmiennoprzecinkowe mają ograniczoną liczbę cyfr, np ..doubles mają 53 bity. Oznacza to, że jeśli masz "bezużyteczne" cyfry, które nie są częścią rozwiązania, ale muszą być przechowywane, tracisz precyzję.

Na przykład (Używamy rodzajów dziesiętne do demonstracji):

2,598765000000000000000000000100 -

2,598765000000000000000000000099

Interesującą częścią jest 100-99 = 1 odpowiedź. Ponieważ 2.598765 jest równy w obu przypadkach, to nie zmienia wyniku, ale marnuje 8 cyfr. Znacznie gorzej, ponieważ komputer nie wie, że cyfry są bezużyteczne, jest zmuszony do przechowywania i 21 zera po nim zeruje, marnując na wszystkich 29 cyfr. Niestety nie ma sposobu na obejście go dla różnic, , ale są też inne przypadki, np. exp (x) -1, który jest funkcją bardzo często występującą w fizyce.

Funkcja exp w pobliżu 0 jest prawie liniowa, ale wymusza 1 jako wiodącą cyfrę. Tak więc z 12 cyfr znaczących exp (0,001) -1 = 1,00100050017 - 1 = 1.00050017e-3

Jeśli zamiast tego wykorzystać expm1() funkcji, należy szereg Taylora:

1 + x + x^2/2 + x^3/6 ...-1 =

x + x^2/2 + x^3/6 =: expm1 (x)

expm1 (0,001) = 1.00500166667e-3

znacznie lepiej.

Drugi problem to funkcje o bardzo stromym zboczu, jak styczna x blisko pi/2. tan (11) ma nachylenie 50000, co oznacza, że ​​każde małe odchylenie spowodowane błędami zaokrąglania zostanie wzmocnione o czynnik 50000! Albo masz osobliwości, np. wynik zbliża się do 0/0, co oznacza, że ​​może mieć dowolną wartość.

W obu przypadkach tworzy się funkcję zastępczą, po prostu prostą funkcję. Nie ma sensu podkreślać różnych podejść do rozwiązania, ponieważ bez szkolenia po prostu nie "zobaczysz" problemu w pierwszej kolejności.

Bardzo dobra książka do nauki i szkolenia: Forman S. Acton: Real Computing made real