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

18

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?

JNL
źródło
2
Czy napotykasz konkretny problem? Istnieje wiele sposobów testowania, w porządku w przypadku niektórych problemów. Pytania, na które można uzyskać wiele odpowiedzi, źle pasują do formatu pytań i odpowiedzi. Byłoby najlepiej, gdybyś mógł zdefiniować swój problem w sposób, który mógłby dać jedną właściwą odpowiedź, zamiast rzucać sieć pomysłów i rekomendacji.
Tworzę aplikację z wieloma obliczeniami matematycznymi. Rozumiem, że testy NUNIT lub JUNIT byłyby dobre, ale chciałbym mieć pomysł, jak podejść do problemów z obliczeniami matematycznymi.
JNL
1
Czy możesz podać przykład obliczenia, które testujesz? Jednym z nich zwykle nie byłoby testowanie jednostkowe surowej matematyki (chyba że testujesz własne typy numeryczne), ale testowanie czegoś podobnego distanceTraveled(startVel, duration, acceleration)byłoby testowane.
Jednym z przykładów będzie zajmowanie miejsc po przecinku. Załóżmy na przykład, że budujemy ścianę ze specjalnymi ustawieniami dla dist x-0 do x = 14.589, a następnie niektóre układy od x = 14.589 do x = koniec ściany. Odległość .589 po konwersji na binarną nie jest taka sama ... Zwłaszcza jeśli dodamy pewne odległości ... np. 14.589 + 0.25 nie będzie równa 14,84 w binarnej .... Mam nadzieję, że nie jest myląca?
JNL
1
@MichaelT dziękuję za edycję pytania. Bardzo mi pomógł. Ponieważ jestem nowy, nie jestem zbyt dobry w tworzeniu ramek na pytania. :) ... Ale wkrótce będzie dobrze.
JNL

Odpowiedzi:

22

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ę.


źródło
2
To dobry początek, ale oczywiście nie rozwiązuje całkowicie problemu zaokrąglania. Liczby niewymierne, takie jak π, e i √2, nie mają reprezentacji ściśle numerycznej; musisz reprezentować je symbolicznie, jeśli chcesz dokładną reprezentację, lub ocenić je tak późno, jak to możliwe, jeśli chcesz zminimalizować błąd zaokrąglania.
Caleb
@Caleb dla irracjonalnych należałoby ocenić je poza te obszary, w których zaokrąglenie może powodować problemy. Na przykład 22/7 ma dokładność do 0,1% pi, 355/113 ma dokładność do 10 ^ -8. Jeśli pracujesz tylko z liczbami do 3 miejsc po przecinku, posiadanie 3,141592653 powinno unikać błędów zaokrąglania przy 3 miejscach po przecinku.
@MichaelT: Aby dodać liczby wymierne, nie musisz znajdować LCM i szybciej go nie ma (i szybciej anulujesz „zera LSB” po, i zawsze w pełni upraszczasz, gdy jest to absolutnie konieczne). W przypadku liczb wymiernych jest to zwykle po prostu sam „licznik / mianownik” lub „wykładnik / mianownik << wykładnik” (a nie „cała część + licznik / mianownik”). Również „zmiennoprzecinkowy punkt stały” jest reprezentacją zmiennoprzecinkową i lepiej byłoby go opisać jako „zmiennoprzecinkowy o dowolnym rozmiarze” (w celu odróżnienia go od „zmiennoprzecinkowego stałego rozmiaru”).
Brendan
niektóre z waszej terminologii są nieco niepewne - zmiennoprzecinkowy punkt stały nie ma sensu - myślę, że próbujesz powiedzieć zmiennoprzecinkowy.
jk.
10

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.

Mason Wheeler
źródło
Obecnie używam VC ++ ... Ale byłbym wdzięczny za wszelkie informacje dotyczące innych języków programowania.
JNL
Nawet bez wartości zmiennoprzecinkowych nadal będziesz mieć problemy.
Czad
2
@Chad Prawda, ale celem nie jest wyeliminowanie problemów z zaokrąglaniem (które zawsze będą istnieć, ponieważ w dowolnej używanej bazie istnieją liczby, które nie mają dokładnej reprezentacji i nie masz nieskończonej pamięci i mocy obliczeniowej), zredukuj do tego stopnia, że ​​nie ma to wpływu na obliczenia, które próbujesz wykonać.
Iker
@Iker Masz rację. Chociaż ani ty, ani osoba zadająca pytanie nie określiłeś, jakie dokładnie obliczenia starają się osiągnąć i jakiej precyzji chcą. Najpierw musi odpowiedzieć na to pytanie, zanim przejdzie do teorii liczb. Samo powiedzenie lot of mathematical calculationsnie jest pomocne ani udzielone odpowiedzi. W zdecydowanej większości przypadków (jeśli nie masz do czynienia z walutą), float powinien naprawdę wystarczyć.
Czad
@Czy to uczciwa kwestia, z pewnością nie ma wystarczającej ilości danych z PO, aby powiedzieć, jaki dokładnie poziom precyzji jest im potrzebny.
Iker
7

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.

cmaster - przywróć monikę
źródło
2

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.

gnasher729
źródło
1
W matematyce zmiennoprzecinkowej nie ma „zdrowego rozsądku”.
whatsisname
Dowiedz się więcej na ten temat.
gnasher729
0

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.

Czad
źródło