Co powoduje błędy zaokrąglania zmiennoprzecinkowego?

62

Wiem, że arytmetyka zmiennoprzecinkowa ma problemy z precyzją. Zwykle pokonuję je, przechodząc do stałej liczby dziesiętnej lub po prostu zaniedbując błąd.

Nie wiem jednak, jakie są przyczyny tej niedokładności. Dlaczego jest tak wiele problemów z zaokrąglaniem liczb zmiennoprzecinkowych?

nmat
źródło
28
Mówiąc ściślej, tak naprawdę nie jest to błąd spowodowany zaokrąglaniem, o który martwi się większość ludzi - to fakt, że binarne zaokrąglanie zmiennoprzecinkowe zachowuje się w nieintuicyjny sposób. Przełączenie na reprezentację dziesiętną może sprawić, że zaokrąglanie będzie zachowywać się w bardziej intuicyjny sposób, ale w zamian prawie zawsze zwiększysz błąd względny (lub będziesz musiał zwiększyć przestrzeń dyskową, aby to zrekompensować).
Daniel Pryden,
12
Moja próba wyjaśnienia najczęstszych nieporozumień: floating-point-gui.de
Michael Borgwardt
myślę, że @DanielPryden znaczy: „Przełączenie na reprezentację [stałoprzecinkową] może sprawić, że zaokrąglanie będzie zachowywać się bardziej intuicyjnie ...” . to, co powoduje problemy z zaokrąglaniem, bez względu na to, czy są to liczby stałe, czy zmiennoprzecinkowe, to skończona szerokość każdego z nich. po prostu w przypadku liczby zmiennoprzecinkowej wielkość błędu zaokrąglania zwykle pozostaje w przybliżeniu proporcjonalna do wielkości zaokrąglanej liczby. (z wyjątkiem sytuacji, gdy stają się naprawdę małe i do „zdenormalizowanych” liczb.)
Robert Bristol-Johnson
@robert: Nie o to mi chodziło. „Błąd”, jaki większość ludzi napotyka na zmiennoprzecinkowy, nie ma nic wspólnego z samym zmiennoprzecinkowym, jest to podstawa. Liczby zmiennoprzecinkowe IEEE-754 używają wykładnika w bazie 2, co oznacza, że ​​liczby ułamkowe zaokrąglają się do potęgi ujemnej dwóch (1/2, 1/16, 1/1024 itd.) Zamiast potęgi ujemnej 10 (1 / 10, 1/1000 itp.) Prowadzi to do nieintuicyjnych wyników, takich jak zaokrąglanie 0,1 do 0,1000001 i podobne problemy.
Daniel Pryden
Możesz wykonywać liczby zmiennoprzecinkowe w bazie 10 - tak decimaldziała typ .NET . Z drugiej strony punkt stały jest inny. Tak długo, jak twój zasięg jest ograniczony, punkt stały jest dobrą odpowiedzią. Jednak ograniczony zakres sprawia, że ​​punkt stały nie nadaje się do wielu zastosowań matematycznych, a implementacje liczb stałych nie są często dobrze zoptymalizowane sprzętowo.
Daniel Pryden

Odpowiedzi:

82

Wynika to z faktu, że niektóre ułamki potrzebują bardzo dużej (lub nawet nieskończonej) liczby miejsc do wyrażenia bez zaokrąglania. Dotyczy to zarówno notacji dziesiętnych, jak i binarnych. Jeśli ograniczysz liczbę miejsc dziesiętnych do wykorzystania w obliczeniach (i unikniesz wykonywania obliczeń w notacji ułamkowej), będziesz musiał zaokrąglić nawet proste wyrażenie jako 1/3 + 1/3. Zamiast pisać 2/3 w rezultacie, musiałbyś napisać 0.33333 + 0.33333 = 0.66666, który nie jest identyczny z 2/3.

W przypadku komputera liczba cyfr jest ograniczona technicznym charakterem pamięci i rejestrów procesora. Używana wewnętrznie notacja binarna powoduje dodatkowe trudności. Komputery zwykle nie mogą wyrażać liczb w notacji ułamkowej, chociaż niektóre języki programowania dodają tę możliwość, co pozwala do pewnego stopnia uniknąć tych problemów.

Co każdy informatyk powinien wiedzieć o arytmetyki zmiennoprzecinkowej

Thorsten Müller
źródło
12
Spot on. Ale chciałbym również zauważyć, że niektóre liczby, które kończą się dziesiętnie, nie kończą się binarnie. W szczególności 0,1 jest liczbą powtarzającą się w postaci binarnej, więc żadna liczba zmiennoprzecinkowa nie może dokładnie reprezentować 0,1.
Jack Aidley,
4
Punkty zmiennoprzecinkowe są przydatne nie tylko w przypadku wielu miejsc po przecinku. 32-bitowe liczby całkowite mogą liczyć tylko do około 4 miliardów, ale 32-bitowa liczba zmiennoprzecinkowa może być prawie nieskończenie duża.
Abhi Beckert
7
W szczególności ułamki, które możemy wyrazić jako dziesiętne skończone, to te, których pierwsza faktoryzacja mianowników zawiera tylko 2 i 5 (np. Możemy wyrazić 3/10 i 7/25, ale nie 11/18). Kiedy przechodzimy do binarnej, tracimy współczynnik 5, tak że tylko wyrażenia rażące (np. 1/4, 3/128) mogą być dokładnie wyrażone.
David Zhang
70

Przede wszystkim błędy zaokrąglania wynikają z faktu, że nieskończoność wszystkich liczb rzeczywistych nie może być reprezentowana przez skończoną pamięć komputera , nie mówiąc już o niewielkim wycinku pamięci, takim jak pojedyncza zmienna zmiennoprzecinkowa , tak wiele przechowywanych liczb jest jedynie przybliżeniem liczba, którą mają reprezentować.

Ponieważ istnieje tylko ograniczona liczba wartości, które nie są przybliżeniem, a każda operacja między przybliżeniem a inną liczbą powoduje przybliżenie, błędy zaokrąglania są prawie nieuniknione .

Ważne jest, aby zdać sobie sprawę, kiedy mogą one powodować problem, i podjąć kroki w celu ograniczenia ryzyka .


Oprócz niezbędnej wiedzy Davida Goldberga , którą każdy informatyk powinien wiedzieć o arytmetyki zmiennoprzecinkowej (ponownie opublikowanej przez Sun / Oracle jako załącznik do Przewodnika po obliczeniach numerycznych ), o której wspomniał Thorsten , dziennik ACCU Overload działał doskonale seria artykułów Richarda Harrisa o Floating Point Blues .

Seria rozpoczęła się od

Obliczenia numeryczne mają wiele pułapek. Richard Harris zaczyna szukać srebrnej kuli.

Smok błędu numerycznego często nie budzi się ze snu, ale jeśli podejdzie nieostrożnie, od czasu do czasu wyrządzi katastrofalne szkody obliczeniom nieostrożnego programisty.

Do tego stopnia, że ​​niektórzy programiści, po zorientowaniu się w nim w lasach arytmetyki zmiennoprzecinkowej IEEE 754, odradzają swoim towarzyszom podróżowanie po tej pięknej ziemi.

W tej serii artykułów zajmiemy się światem obliczeń numerycznych, porównując arytmetykę zmiennoprzecinkową z niektórymi technikami, które zostały zaproponowane jako bezpieczniejsze zamienniki. Dowiemy się, że terytorium smoka rzeczywiście daleko sięga i że w ogóle musimy stąpać ostrożnie, jeśli boimy się jego niszczycielskiej uwagi.

Richard zaczyna od wyjaśnienia taksonomii liczb rzeczywistych, racjonalnych, irracjonalnych, algebraicznych i transcendentalnych. Następnie wyjaśnia objaśnienia dotyczące reprezentacji IEEE754, zanim przejdzie do błędu anulowania i problemów z kolejnością wykonywania.

Jeśli nie przeczytasz głębiej, będziesz miał doskonałe uziemienie w problemach związanych z liczbami zmiennoprzecinkowymi.

Jeśli chcesz dowiedzieć się więcej, kontynuuje

Następnie przełącza się na próbę pomocy w wyleczeniu bluesa

i na koniec jest

Warto zapoznać się z całą serią artykułów, a przy całkowitej liczbie 66 stron są one nadal mniejsze niż 77 stron artykułu Goldberga .

Chociaż ta seria obejmuje wiele tego samego obszaru, uważam, że jest ona bardziej dostępna niż artykuł Goldberga . Po przeczytaniu wcześniejszych artykułów Richardsa łatwiej zrozumiałem bardziej złożone części artykułu. Po tych wczesnych artykułach Richard rozgrywa się w wielu interesujących obszarach, których nie porusza artykuł Goldberga.


Jak to powiedzą ak wspomniane w komentarzach:

Jako autor tych artykułów chciałbym wspomnieć, że stworzyłem ich interaktywne wersje na moim blogu www.thusspakeak.com, poczynając od sospakeak.com/ak/2013/06 .

Mark Booth
źródło
1
Jako autor tych artykułów chciałbym wspomnieć, że stworzyłem ich interaktywne wersje na moim blogu www.thusspakeak.com, poczynając od sospakeak.com/ak/2013/06 .
tak powiedział ak
Dzięki @ sospakea.k. Dodałem notatkę do mojej odpowiedzi, a te interaktywne elementy działają bardzo ładnie.
Mark Booth
12

Cóż, Thorsten ma ostateczny link . Dodałbym:

Każda forma reprezentacji będzie miała błąd zaokrąglania dla pewnej liczby. Spróbuj wyrazić 1/3 w liczbach zmiennoprzecinkowych IEEE lub w systemie dziesiętnym. Żaden nie może tego zrobić dokładnie. Wykracza to poza udzielenie odpowiedzi na pytanie, ale z powodzeniem zastosowałem tę zasadę:

  • Przechowuj wartości wprowadzane przez użytkownika w postaci dziesiętnej (ponieważ prawie na pewno wprowadzono je w postaci dziesiętnej - bardzo niewielu użytkowników będzie używać wartości binarnych lub szesnastkowych). W ten sposób zawsze masz dokładną reprezentację wprowadzoną przez użytkownika.
  • Jeśli musisz przechowywać ułamki wprowadzone przez użytkownika, przechowuj licznik i mianownik (również dziesiętnie)
  • Jeśli masz system z wieloma jednostkami miary dla tej samej ilości (np. Celsjusza / Fahrenheita), a użytkownik może wprowadzić oba, zapisz wprowadzoną wartość i jednostki, w których je wprowadził. Nie próbuj konwertować i zapisywać jako pojedyncza reprezentacja, chyba że możesz to zrobić bez utraty precyzji / dokładności. Użyj zapisanej wartości i jednostek we wszystkich obliczeniach.
  • Przechowuj wygenerowane maszynowo wartości zmiennoprzecinkowe IEEE (mogą to być liczby generowane przez elektroniczne urządzenie pomiarowe, takie jak czujnik analogowy z przetwornikiem A / C, lub nieuzasadniony wynik obliczeń). Zauważ, że nie ma to zastosowania, jeśli odczytujesz czujnik przez połączenie szeregowe i już podaje on wartość w formacie dziesiętnym (np. 18,2 C).
  • Sumy widoczne dla użytkownika przechowuj w systemie dziesiętnym (np. Saldo konta bankowego). Zaokrąglij odpowiednio, ale użyj tej wartości jako wartości ostatecznej dla wszystkich przyszłych obliczeń.
Scott Whitlock
źródło
Dodałbym: Rozważ użycie pakietu matematycznego o dowolnej precyzji, takiego jak ARPREC lub decNumber.
Blrfl,
Nie dziesiętne (w przeciwieństwie do binarnych) ma wiele zalet dla wartości całkowitych, takich jak licznik i mianownik ułamka. Albo może przechowywać dokładne wartości całkowite, a binarne jest bardziej wydajne. Konwersja w obie strony dla danych wejściowych i wyjściowych wiąże się z pewnymi kosztami, ale prawdopodobnie będzie to kosztowane przez fizyczne wykonanie operacji we / wy.
Keith Thompson
10

Wydaje się, że do tej pory nie wspomniano o koncepcjach niestabilnego algorytmu i źle uwarunkowanego problemu . Najpierw zajmę się tym pierwszym, ponieważ wydaje się, że jest to częstsza pułapka dla początkujących numerycy.

Rozważ obliczenie mocy (wzajemności) złotego podziału φ=0.61803…; jednym z możliwych sposobów jest skorzystanie z formuły rekurencyjnej φ^n=φ^(n-2)-φ^(n-1), zaczynając od φ^0=1i φ^1=φ. Jeśli uruchomisz tę rekurencję w swoim ulubionym środowisku komputerowym i porównasz wyniki z dokładnie oszacowanymi mocami, zauważysz powolną erozję znaczących liczb. Oto, co dzieje się na przykład w Mathematica :

ph = N[1/GoldenRatio];  
Nest[Append[#1, #1[[-2]] - #1[[-1]]] & , {1, ph}, 50] - ph^Range[0, 51]  
{0., 0., 1.1102230246251565*^-16, -5.551115123125783*^-17, 2.220446049250313*^-16, 
-2.3592239273284576*^-16, 4.85722573273506*^-16, -7.147060721024445*^-16, 
1.2073675392798577*^-15, -1.916869440954372*^-15, 3.1259717037102064*^-15, 
-5.0411064211886014*^-15, 8.16837916750579*^-15, -1.3209051907825398*^-14, 
2.1377864756200182*^-14, -3.458669982359108*^-14, 5.596472721011714*^-14, 
-9.055131861349097*^-14, 1.465160458236081*^-13, -2.370673237795176*^-13, 
3.835834102607072*^-13, -6.206507137114341*^-13, 1.004234127360273*^-12, 
-1.6248848342954435*^-12, 2.6291189633497825*^-12, -4.254003796798193*^-12, 
6.883122762265558*^-12, -1.1137126558640235*^-11, 1.8020249321541067*^-11, 
-2.9157375879969544*^-11, 4.717762520172237*^-11, -7.633500108148015*^-11, 
1.23512626283229*^-10, -1.9984762736468268*^-10, 3.233602536479646*^-10, 
-5.232078810126407*^-10, 8.465681346606119*^-10, -1.3697760156732426*^-9, 
2.216344150333856*^-9, -3.5861201660070964*^-9, 5.802464316340953*^-9, 
-9.388584482348049*^-9, 1.5191048798689004*^-8, -2.457963328103705*^-8, 
3.9770682079726053*^-8, -6.43503153607631*^-8, 1.0412099744048916*^-7, 
-1.6847131280125227*^-7, 2.725923102417414*^-7, -4.4106362304299367*^-7, 
7.136559332847351*^-7, -1.1547195563277288*^-6}

Podobny wynik dla φ^41ma zły znak, a nawet wcześniej, obliczone i rzeczywiste wartości dla φ^39udziału nie mają wspólnych cyfr ( 3.484899258054952* ^ - 9 for the computed version against the true value7.071019424062048 *^-9). Algorytm jest więc niestabilny i nie należy używać tej formuły rekurencyjnej w niedokładnej arytmetyki. Wynika to z wrodzonej natury formuły rekurencyjnej: istnieje rozwiązanie „zanikające” i „rosnące” tej rekurencji i próbuje się obliczyć rozwiązanie „rozkładające się” według rozwiązania naprzód, gdy istnieje alternatywne rozwiązanie „rosnące” na smutek numeryczny. Należy zatem upewnić się, że jego / jej algorytmy numeryczne są stabilne.

Przejdźmy teraz do koncepcji źle uwarunkowanego problemu: chociaż może istnieć stabilny sposób zrobienia czegoś numerycznie, bardzo możliwe, że Twój problem nie może zostać rozwiązany przez algorytm. Jest to wina samego problemu, a nie metody rozwiązania. Kanonicznym przykładem numerycznym jest rozwiązanie równań liniowych obejmujących tak zwaną „macierz Hilberta”:

Macierz Hilberta

Matryca jest kanonicznym przykładem źle uwarunkowanej matrycy: próba rozwiązania układu za pomocą dużej matrycy Hilberta może zwrócić niedokładne rozwiązanie.

Oto demonstracja Mathematica : porównaj wyniki dokładnej arytmetyki

Table[LinearSolve[HilbertMatrix[n], HilbertMatrix[n].ConstantArray[1, n]], {n, 2, 12}]
{{1, 1}, {1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 
  1}, {1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1,
   1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 
  1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}

i niedokładna arytmetyka

Table[LinearSolve[N[HilbertMatrix[n]], N[HilbertMatrix[n].ConstantArray[1, n]]], {n, 2, 12}]
{{1., 1.}, {1., 1., 1.}, {1., 1., 1., 1.}, {1., 1., 1., 1., 1.},  
  {1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1.}, 
  {1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1., 1.},  
  {1., 1., 1., 0.99997, 1.00014, 0.999618, 1.00062, 0.9994, 1.00031, 
  0.999931}, {1., 1., 0.999995, 1.00006, 0.999658, 1.00122, 0.997327, 
  1.00367, 0.996932, 1.00143, 0.999717}, {1., 1., 0.999986, 1.00022, 
  0.998241, 1.00831, 0.975462, 1.0466, 0.94311, 1.04312, 0.981529, 
  1.00342}}

(Jeśli wypróbowałeś to w Mathematica , zauważysz kilka komunikatów o błędach ostrzegających o pojawieniu się złego warunkowania).

W obu przypadkach zwykłe zwiększenie precyzji nie jest lekarstwem; opóźni to nieuchronną erozję liczb.

Z tym możesz się spotkać. Rozwiązania mogą być trudne: po pierwsze albo wrócisz do deski kreślarskiej, albo przejrzysz czasopisma / książki / cokolwiek, aby znaleźć, czy ktoś wymyślił lepsze rozwiązanie niż ty; po drugie, albo poddajesz się, albo przeformułowujesz swój problem na coś łatwiejszego do rozwiązania.


Zostawię ci cytat z Dianne O'Leary:

Życie może rzucić nam kilka źle uwarunkowanych problemów, ale nie ma dobrego powodu, aby zadowolić się niestabilnym algorytmem.


źródło
9

ponieważ podstawowych liczb dziesiętnych nie można wyrazić w podstawie 2

lub innymi słowy 1/10 nie może zostać przekształcony w ułamek o potędze 2 w mianowniku (którym w istocie są liczby zmiennoprzecinkowe)

maniak zapadkowy
źródło
11
Nie do końca prawda: 0,5 i 0,25 można wyrazić w podstawie 2. Myślę, że masz na myśli „nie wszystkie dziesiętne liczby dziesiętne”.
Scott Whitlock,
3
Dokładniej. Nie wszystkie liczby ułamkowe mogą być dokładnie przedstawione za pomocą notacji zmiennoprzecinkowej (tzn. Z. Zarówno podstawa 2, jak i podstawa 10 mają dokładnie ten problem). Spróbuj zrobić 9*3.3333333w systemie dziesiętnym i dopasuj go do9*3 1/3
Martin York,
1
Jest to najczęstsze źródło zamieszania zmiennoprzecinkowego. .1 + .1 != .2ponieważ używane jest zmiennoprzecinkowe kodowanie binarne, a nie dziesiętne.
Sean McMillan
@SeanMcMillan: A 1.0/3.0*3.0 != 1.0ponieważ stosowane jest zmiennoprzecinkowe kodowanie binarne, a nie trójkowe.
Keith Thompson,
8

W matematyce istnieje nieskończenie wiele liczb wymiernych. Zmienna 32-bitowa może mieć tylko 2 32 różne wartości, a zmienna 64-bitowa tylko 2 64 wartości. Dlatego istnieje nieskończenie wiele liczb wymiernych, które nie mają dokładnej reprezentacji.

Moglibyśmy wymyślić schematy, które pozwoliłyby nam idealnie reprezentować 1/3 lub 1/100. Okazuje się, że dla wielu praktycznych celów nie jest to zbyt przydatne. Jest jeden wielki wyjątek: w finansach często pojawiają się ułamki dziesiętne. Dzieje się tak głównie dlatego, że finanse są zasadniczo działalnością ludzką, a nie fizyczną.

Dlatego zazwyczaj wybieramy binarne zmiennoprzecinkowe i zaokrąglamy każdą wartość, której nie można przedstawić w postaci binarnej. Ale w finansach czasami wybieramy zmiennoprzecinkowe dziesiętne i zaokrąglamy wartości do najbliższej wartości dziesiętnej.

MSalters
źródło
2
Co gorsza, podczas gdy nieskończona (licznie nieskończona) ilość pamięci umożliwiłaby przedstawienie wszystkich racjonalności, nie wystarczyłaby reprezentacja rzeczywistości. Co gorsza, prawie wszystkie liczby rzeczywiste nie są liczbami obliczalnymi. Najlepsze, co możemy zrobić ze skończoną ilością pamięci, to przybliżenie podzbioru skończonego zakresu liczb rzeczywistych.
David Hammen
4
@Kevin: Mówisz o liczbach obliczalnych, które są niewielkim podzbiorem (podzbiorem o zerowej wartości) reali.
David Hammen,
1
+1 za najbardziej podstawowe wyjaśnienie: Próbujesz reprezentować nieskończoną liczbę liczb o skończonej liczbie bitów.
Raku,
1
@DavidHammen: Liczby obliczalne to niewielki podzbiór (liczący zero) liczb rzeczywistych - ale każda liczba, z którą kiedykolwiek pracujesz w programie, jest z definicji obliczalna.
Keith Thompson
3
@Giorgio: Jeśli wybierzesz odpowiednią reprezentację, pierwiastek kwadratowy z 2 będzie reprezentowany na przykład jako ciąg "√2". (Mój stary kalkulator HP-48 był w stanie to zrobić, a dokładność tej wartości do kwadratu dała dokładnie wynik 2.0). Istnieje tylko policzalna nieskończoność reprezentowalnych liczb rzeczywistych dla dowolnej skończonej reprezentacji - ale żadne obliczenia nie mogą dać liczby, która nie jest, w zasadzie reprezentatywny. W praktyce binarna zmiennoprzecinkowa drastycznie ogranicza zbiór reprezentatywnych liczb, z korzyścią niesamowitej prędkości i niewielkiej pamięci względem reprezentacji symbolicznych.
Keith Thompson
-2

jedynym naprawdę oczywistym „problemem zaokrąglania” liczb zmiennoprzecinkowych, o którym myślę, są filtry średniej ruchomej:

$$ \ begin {align} y [n] & = \ frac {1} {N} \ sum \ limit_ {i = 0} ^ {N-1} x [ni] \ & = y [n-1] + \ frac {1} {N} (x [n] - x [nN]) \ \ end {align} $$

aby to działało bez narastania hałasu, musisz upewnić się, że $ x [n] $ dodany w bieżących próbkach jest dokładnie taki sam jak $ x [nN] $, który odejmiesz w próbkach $ N $ przyszłość. jeśli tak nie jest, to co jest inne, to mała gnójka, która utknęła w linii opóźnienia i nigdy nie wyjdzie. to dlatego, że ten filtr średniej ruchomej jest faktycznie zbudowany z IIR, który ma marginalnie stabilny biegun przy $ z = 1 $ i zero, które anuluje go wewnątrz. ale jest to integrator i wszelkie bzdury, które zostaną zintegrowane, a nie całkowicie usunięte, będą istnieć w sumie integratora na zawsze. w tym przypadku punkt stały nie ma tego samego problemu, co liczby zmiennoprzecinkowe.

Robert Bristol-Johnson
źródło
hej, czy znaczniki matematyczne $ LaTeX $ nie działają na forum prog.SE ??? to naprawdę kiepskie, jeśli tak nie jest.
Robert Bristol-Johnson
1
Zobacz to na meta.SO i powiązanych pytaniach
AakashM