Rozwiązania błędów zaokrąglania zmiennoprzecinkowego

Tworząc aplikację, która zajmuje się licznymi obliczeniami matematycznymi, napotkałem problem polegający na tym, że niektóre liczby powodują błędy zaokrąglania.

Rozumiem, że zmiennoprzecinkowe nie jest dokładne , ale problem polega na tym , jak postępować z dokładnymi liczbami, aby mieć pewność, że przy ich wykonywaniu obliczenia zaokrąglanie zmiennoprzecinkowe nie spowoduje żadnych problemów?

Istnieją trzy podstawowe podejścia do tworzenia alternatywnych typów numerycznych, które są wolne od zaokrąglania zmiennoprzecinkowego. Wspólnym motywem jest to, że używają matematyki liczb całkowitych zamiast na różne sposoby.

Racjonalne

Reprezentuj liczbę jako całość i liczbę wymierną za pomocą licznika i mianownika. Liczba 15.589będzie reprezentowana jako w: 15; n: 589; d:1000.

Po dodaniu do 0,25 (czyli jest w: 0; n: 1; d: 4) obejmuje to obliczenie LCM, a następnie dodanie dwóch liczb. Działa to dobrze w wielu sytuacjach, ale może prowadzić do bardzo dużych liczb, gdy pracujesz z wieloma liczbami wymiernymi, które są względnie pierwsze.

Punkt stały

Masz całą część i część dziesiętną. Wszystkie liczby są zaokrąglone (jest to słowo - ale wiesz, gdzie ono jest) z tą precyzją. Na przykład możesz mieć stały punkt z 3 miejscami po przecinku. 15.589+ 0.250staje się sumowaniem 589 + 250 % 1000dla części dziesiętnej (a następnie dla każdego przeniesienia do całej części). Działa to bardzo dobrze z istniejącymi bazami danych. Jak wspomniano, istnieje zaokrąglenie, ale wiesz, gdzie to jest i możesz je określić tak, aby było bardziej precyzyjne niż jest to potrzebne (mierzysz tylko do 3 miejsc po przecinku, więc ustaw je na 4).

Zmienny punkt stały

Przechowuj wartość i precyzję. 15.589jest przechowywany jak 15589dla wartości i 3precyzji, podczas gdy 0.25jest przechowywany jako 25i 2. Może to obsłużyć dowolną precyzję. Ja wierzę to jest to, co wewnętrzne zastosowań Javy BigDecimal (nie spojrzał na nią niedawna) zastosowań. W pewnym momencie będziesz chciał odzyskać go z tego formatu i wyświetlić - i może to wymagać zaokrąglania (ponownie kontrolujesz, gdzie to jest).

Po określeniu wyboru reprezentacji możesz albo znaleźć istniejące biblioteki stron trzecich, które tego używają, albo napisać własne. Pisząc własną, sprawdź ją i upewnij się, że poprawnie wykonujesz matematykę.

Jeśli wartości zmiennoprzecinkowe mają problemy z zaokrąglaniem, a nie chcesz mieć problemów z zaokrąglaniem, logicznie wynika, że ​​jedynym sposobem działania jest niestosowanie wartości zmiennoprzecinkowych.

Teraz pojawia się pytanie: „jak mam wykonać matematykę z wartościami niecałkowitymi bez zmiennych zmiennoprzecinkowych?” Odpowiedź jest z typami danych o dowolnej precyzji . Obliczenia są wolniejsze, ponieważ muszą być zaimplementowane w oprogramowaniu zamiast w sprzęcie, ale są dokładne. Nie powiedziałeś, jakiego języka używasz, więc nie mogę polecić pakietu, ale dla większości popularnych języków programowania dostępne są biblioteki o dowolnej precyzji.

Arytmetyka zmiennoprzecinkowa jest zwykle dość dokładna (15 cyfr dziesiętnych dla a double) i dość elastyczna. Problemy pojawiają się, gdy robisz matematykę, co znacznie zmniejsza liczbę cyfr precyzji. Oto kilka przykładów:

• Anulowanie po odjęciu: 1234567890.12345 - 1234567890.12300wynik 0.0045ma tylko dwie cyfry dziesiętne precyzji. Uderza to za każdym razem, gdy odejmiesz dwie liczby o podobnej wielkości.

• Połknięcie precyzji: 1234567890.12345 + 0.123456789012345ocenia 1234567890.24691, ostatnie dziesięć cyfr drugiego operandu są tracone.

• Mnożenie: Jeśli pomnożysz dwie 15-cyfrowe liczby, wynik ma 30 cyfr, które należy zapisać. Ale nie możesz ich przechowywać, więc ostatnie 15 bitów zostanie utraconych. Jest to szczególnie uciążliwe w połączeniu z sqrt()(jak w sqrt(x*x + y*y): Wynik będzie miał jedynie 7,5 cyfry dokładności.

Są to główne pułapki, o których musisz wiedzieć. A kiedy będziesz ich świadomy, możesz spróbować sformułować swoją matematykę w sposób, który pozwoli im ich uniknąć. Na przykład, jeśli chcesz wielokrotnie zwiększać wartość w pętli, unikaj:

for(double f = f0; f < f1; f += df) {

Po kilku iteracjach większy fpołknie część precyzji df. Co gorsza, błędy sumują się, co prowadzi do sytuacji, w której mniejszy dfmoże prowadzić do gorszych wyników ogólnych. Lepiej napisz to:

for(int i = 0; i < (f1 - f0)/df; i++) {
    double f = f0 + i*df;

Ponieważ łączymy przyrosty w jednym pomnożeniu, wynik fbędzie dokładny do 15 cyfr dziesiętnych.

To tylko przykład, istnieją inne sposoby uniknięcia utraty precyzji z innych powodów. Ale bardzo pomaga już myśleć o wielkości zaangażowanych wartości i wyobrażać sobie, co by się stało, gdybyś zrobił matematykę za pomocą pióra i papieru, zaokrąglając do stałej liczby cyfr po każdym kroku.

Jak upewnić się, że nie masz problemów: Dowiedz się o problemach arytmetycznych zmiennoprzecinkowych lub zatrudnij kogoś, kto je ma, lub zachowaj zdrowy rozsądek.

Pierwszym problemem jest precyzja. W wielu językach masz „zmiennoprzecinkowe” i „podwójne” (podwójna pozycja oznacza „podwójną precyzję”), aw wielu przypadkach „zmiennoprzecinkowa” daje około 7 cyfr precyzji, a podwójna daje 15. Zdrowy rozsądek jest taki, że jeśli masz W sytuacji, gdy dokładność może być problemem, 15 cyfr jest o wiele lepszym rozwiązaniem niż 7 cyfr. W wielu nieco problematycznych sytuacjach użycie „podwójnego” oznacza, że ​​ci się to udaje, a „float” oznacza, że ​​nie. Załóżmy, że kapitalizacja rynkowa firmy wynosi 700 miliardów dolarów. Przedstaw to w liczbach zmiennoprzecinkowych, a najniższy bit to 65536 USD. Reprezentuj to używając podwójnego, a najniższy bit to około 0,012 centów. Więc jeśli naprawdę nie wiesz, co robisz, używasz podwójnego, a nie zmiennoprzecinkowego.

Drugi problem jest bardziej kwestią zasad. Jeśli wykonasz dwa różne obliczenia, które powinny dać ten sam wynik, często nie robią tego z powodu błędów zaokrąglania. Dwa wyniki, które powinny być równe, będą „prawie równe”. Jeśli dwa wyniki są blisko siebie, rzeczywiste wartości mogą być równe. A może nie. Musisz o tym pamiętać i powinieneś pisać i używać funkcji, które mówią, że „x jest zdecydowanie większy niż y” lub „x jest zdecydowanie mniejszy niż y” lub „x i y mogą być równe”.

Ten problem staje się znacznie poważniejszy, jeśli użyjesz zaokrąglania, na przykład „zaokrąglaj x w dół do najbliższej liczby całkowitej”. Jeśli pomnożymy 120 * 0,05, wynik powinien wynosić 6, ale otrzymamy „pewną liczbę bardzo zbliżoną do 6”. Jeśli następnie „zaokrąglisz w dół do najbliższej liczby całkowitej”, ta „liczba bardzo bliska 6” może być „nieco mniejsza niż 6” i zostać zaokrąglona do 5. Zauważ, że nie ma znaczenia, ile precyzji masz. Nie ma znaczenia, jak blisko 6 jest twój wynik, o ile jest on mniejszy niż 6.

Po trzecie, niektóre problemy są trudne . Oznacza to, że nie ma szybkiej i łatwej reguły. Jeśli twój kompilator obsługuje „długi podwójny” z większą precyzją, możesz użyć „długiego podwójnego” i zobaczyć, czy to robi różnicę. Jeśli to nie robi różnicy, oznacza to, że jesteś w porządku lub masz naprawdę trudny problem. Jeśli robi to taką różnicę, jakiej byś się spodziewał (jak zmiana na 12 miejsc po przecinku), prawdopodobnie nic ci nie jest. Jeśli to naprawdę zmienia wyniki, masz problem. Zapytaj o pomoc.

Większość ludzi popełnia błąd, gdy widzą podwójne, krzyczą BigDecimal, podczas gdy w rzeczywistości przenieśli problem gdzie indziej. Podwójne daje Bit znaku: 1 bit, Szerokość wykładnika: 11 bitów. Znacząca precyzja: 53 bity (52 jawnie zapisane). Ze względu na naturę podwójności, im większy interger, tym tracisz względną dokładność. Aby obliczyć względną dokładność, której używamy tutaj, poniżej.

Względną dokładność podwójności w obliczeniach wykorzystujemy następującą foluma 2 ^ E <= abs (X) <2 ^ (E + 1)

epsilon = 2 ^ (E-10)% Dla pływaka 16-bitowego (połowa precyzji)

 Accuracy Power | Accuracy -/+| Maximum Power | Max Interger Value
 2^-1           | 0.5         | 2^51          | 2.2518E+15
 2^-5           | 0.03125     | 2^47          | 1.40737E+14
 2^-10          | 0.000976563 | 2^42          | 4.39805E+12
 2^-15          | 3.05176E-05 | 2^37          | 1.37439E+11
 2^-20          | 9.53674E-07 | 2^32          | 4294967296
 2^-25          | 2.98023E-08 | 2^27          | 134217728
 2^-30          | 9.31323E-10 | 2^22          | 4194304
 2^-35          | 2.91038E-11 | 2^17          | 131072
 2^-40          | 9.09495E-13 | 2^12          | 4096
 2^-45          | 2.84217E-14 | 2^7           | 128
 2^-50          | 8.88178E-16 | 2^2           | 4

Innymi słowy Jeśli chcesz uzyskać dokładność +/- 0,5 (lub 2 ^ -1), maksymalny rozmiar, jaki może być liczbą, to 2 ^ 52. Każda większa niż to, a odległość między liczbami zmiennoprzecinkowymi jest większa niż 0,5.

Jeśli chcesz uzyskać dokładność +/- 0,0005 (około 2 ^ -11), maksymalny rozmiar, jaki może być liczbą, to 2 ^ 42. Każda większa niż to, a odległość między liczbami zmiennoprzecinkowymi jest większa niż 0,0005.

Naprawdę nie mogę udzielić lepszej odpowiedzi niż ta. Użytkownik będzie musiał ustalić, jakiej precyzji potrzebuje, wykonując niezbędne obliczenia i ich wartość jednostkową (metry, stopy, cale, mm, cm). W zdecydowanej większości przypadków pływanie wystarczy do prostych symulacji w zależności od skali świata, który chcesz symulować.

Chociaż należy coś powiedzieć, jeśli zamierzasz symulować świat o wymiarach 100 na 100 metrów, będziesz miał gdzieś dokładność rzędu 2 ^ -45. Nie chodzi nawet o to, w jaki sposób nowoczesne FPU w procesorach wykonają obliczenia poza rodzimym rozmiarem typu i dopiero po zakończeniu obliczeń zaokrąglą (w zależności od trybu zaokrąglania FPU) do rozmiaru rodzimego.