Co powoduje błędy zaokrąglania zmiennoprzecinkowego?

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?

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

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

• Będziesz musiał pomyśleć! wprzeciążeniu # 99( pdf , p5-10):

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

• Dlaczego ustalony punkt nie wyleczy bluesa zmiennoprzecinkowego wprzeciążeniu # 100( pdf , p15-22)
• Dlaczego Rationals nie wyleczy bluesa zmiennoprzecinkowego wprzeciążeniu # 101( pdf , p9-13)
• Dlaczego algebra komputerowa nie wyleczy bluesa zmiennoprzecinkowego wprzeciążeniu # 102( pdf , p9-14).
• Dlaczego arytmetyka interwałowa nie wyleczy bluesa zmiennoprzecinkowego wprzeciążeniu 103( pdf , p19-24)

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

• Dlaczego [wstaw tutaj algorytm] nie wyleczy bluesa z rachunku wprzeciążeniu 104( pdf , p22-24).
• Dlaczego różnice skończone nie wyleczy bluesa w rachunku przeciążeniowym 105( pdf , p5-12).
• Dlaczego aproksymacja wielomianowa nie wyleczy bluesa w rachunku przeciążeniowym 106( pdf , s. 16–25).
• Dlaczego algebra komputerowa nie wyleczy bluesa wprzeciążeniu 107( pdf , s. 15–20).

i na koniec jest

• Dlaczego automatyczne różnicowanie nie wyleczy bluesa w przebieguprzeciążenia 108( pdf , p4-11).

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 .

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

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”:

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.

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)

W matematyce istnieje nieskończenie wiele liczb wymiernych. Zmienna 32-bitowa może mieć tylko 2 ³² różne wartości, a zmienna 64-bitowa tylko 2 ⁶⁴ 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.

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.