Co powoduje błędy zaokrągleń zmiennoprzecinkowych?

Dzieje się tak, ponieważ niektóre ułamki wymagają bardzo dużej (lub nawet nieskończonej) liczby miejsc, które mają być wyrażone bez zaokrąglania. Dotyczy to zarówno notacji dziesiętnej, jak i binarnej lub jakiejkolwiek innej. Jeśli ograniczysz liczbę miejsc dziesiętnych do obliczeń (i unikniesz wykonywania obliczeń w notacji ułamkowej), musiałbyś zaokrąglić nawet proste wyrażenie jako 1/3 + 1/3. Zamiast wpisywać 2/3 w rezultacie musiałbyś wpisać 0,33333 + 0,33333 = 0,66666, co nie jest identyczne z 2/3.

W przypadku komputera liczba cyfr jest ograniczona ze względów technicznych pamięci i rejestrów procesora. Notacja binarna używana wewnętrznie stwarza więcej trudności. Komputery zwykle nie mogą „t wyrażać liczb w notacji ułamkowej, chociaż niektóre języki programowania dodają tę możliwość, która pozwala w pewnym stopniu uniknąć tych problemów.

Co każdy informatyk powinien wiedzieć o arytmetyce zmiennoprzecinkowej

Komentarze

• Dobrze. Ale chciałbym również zauważyć, że niektóre liczby, zakończ w systemie dziesiętnym don ' t zakończ w systemie dwójkowym. W szczególności 0,1 jest liczbą powtarzającą się w systemie binarnym, więc żadna zmiennoprzecinkowa liczba binarna nie może dokładnie odpowiadać 0,1.
• Liczba zmiennoprzecinkowa punkty nie są ' użyteczne tylko dla wielu miejsc po przecinku. 32-bitowe liczby całkowite mogą liczyć tylko do około 4 miliardów, ale 32-bitowe liczby zmiennoprzecinkowe mogą być prawie nieskończenie duże.
• W szczególności ułamki, które możemy wyrazić jako skończone ułamki dziesiętne, to te, których mianowniki ' na czynniki pierwsze zawierają tylko 2 i 5 (np. możemy wyrazić 3/10 i 7/25 , ale nie 11/18). Kiedy przechodzimy do binarności, tracimy współczynnik 5, więc tylko wymierne diadyczne (np. 1/4, 3/128) można wyrazić dokładnie.

Przede wszystkim błędy zaokrągleń wynikają z faktu, że nieskończoność wszystkich liczb rzeczywistych nie może być reprezentowane przez skończoną pamięć komputera , nie mówiąc już o małym kawałku pamięci, takim jak pojedyncza zmienna zmiennoprzecinkowa , więc wiele przechowywanych liczb jest po prostu przybliżenia liczby, którą mają przedstawiać.

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

Ważne należy uświadomić sobie, kiedy mogą spowodować problem i podjąć kroki w celu ograniczenia ryzyka .

Oprócz David Goldberg „co najważniejsze Co każdy informatyk t Powinien wiedzieć o arytmetyce zmiennoprzecinkowej (ponownie opublikowany przez Sun / Oracle jako dodatek do ich Numerical Computation Guide ), o którym wspomniał thorsten , ACCU dziennik Przeciążenie opublikował doskonałą serię artykułów autorstwa Richarda Harrisa na temat Floating Point Blues .

Seria rozpoczęła się od

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

Współczynnik numeryczny mputing ma wiele pułapek. Richard Harris zaczyna szukać srebrnej kuli.

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

Do tego stopnia, że niektórzy programiści, którzy spotkali go w lasach arytmetyki zmiennoprzecinkowej IEEE 754, odradzają swoim kolegom podróżowanie po tym pięknym kraju.

W tej serii artykułów zbadamy świat obliczeń numerycznych, kontrastując arytmetykę zmiennoprzecinkową z niektórymi technikami, które zostały zaproponowane jako bezpieczniejsze dla niej zamienniki. Dowiemy się, że terytorium smoka rzeczywiście sięga daleko i ogólnie musimy postępować ostrożnie, jeśli boimy się jego druzgocąca uwaga.

Richard rozpoczyna od wyjaśnienia taksonomii liczb rzeczywistych, racjonalnej, irracjonalnej, algebraicznej i transcendentalnej. Następnie wyjaśnia reprezentację IEEE754, zanim przejdzie do błędu anulowania i problemów z kolejnością wykonywania.

Jeśli nie czytasz więcej niż to, będziesz miał doskonałe podstawy w problemach związanych z liczbami zmiennoprzecinkowymi .

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

• Dlaczego stały punkt nie wygrał” t nie wyleczysz zmiennoprzecinkowego bluesa w Przeciążenie # 100 ( pdf , p15-22)
• Dlaczego Rationals nie Wylecz swój zmiennoprzecinkowy smutek w Przeciążenie nr 101 ( pdf , p9-13)
• Dlaczego algebra komputerowa nie wyleczy z bluesa zmiennoprzecinkowego in Przeciążenie # 102 ( pdf , p9- 14).
• Dlaczego arytmetyka interwałowa nie wyleczy twoich smutków zmiennoprzecinkowych in Przeciążenie 103 ( pdf , str. 19-24)

Następnie przechodzi do próby pomocy w wyleczeniu Calculus Blues

• Dlaczego [wstaw algorytm tutaj] nie wyleczy z bluesa Calculus in Przeciążenie 104 ( pdf , str. 22-24).
• Dlaczego różnice skończone nie wyleczy z bluesa z rachunku różniczkowego in Przeciążenie 105 ( pdf , p5-12).
• Dlaczego aproksymacja wielomianowa nie wygrała „t Wylecz blues z rachunku różniczkowego w Przeciążenie 106 ( pdf , s16-25).
• Dlaczego algebra komputerowa nie wyleczy bluesa w rachunku różniczkowym w Przeciążenie 107 ( pdf , s.15-20).

i wreszcie

• Dlaczego automatyczne różnicowanie nie wyleczy bluesa z rachunku różniczkowego in Przeciążenie 108 ( pdf , str4-11).

Cała seria artykułów jest warto się przyjrzeć, a łącznie 66 stron jest nadal mniejszych niż 77 stron w gazecie Goldberga .

Chociaż to Seria obejmuje wiele tego samego tematu, wydaje mi się, że jest bardziej dostępna niż papier Goldberga . Łatwiej było mi również zrozumieć bardziej złożone części artykułu po przeczytaniu wcześniejszych artykułów Richardsa i po tych wczesnych artykułach Richard rozgałęzia się w wielu interesujących obszarach, których nie poruszył artykuł Goldberga.

Jak tak powiedział ak wspomniany w komentarzach:

Jako autor artykuły, o których chciałbym wspomnieć, że utworzyłem ich interaktywne wersje na moim blogu www.thusspakeak.com , zaczynając od zatemspakeak.com/ak/2013/06 .

Komentarze

• Jako autor tych artykułów chciałbym ' wspomnieć, że utworzyłem ich interaktywne wersje na moim blogu www.thusspakeak.com, zaczynając od zatemspakeak.com/ak/2013/06 .
• Dzięki @ sospakea.k. ' dodałem notatkę na moją odpowiedź i mimo ponieważ elementy interaktywne działają bardzo dobrze.

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

Każda forma reprezentacji będzie miała błąd zaokrąglenia dla pewnej liczby. Spróbuj wyrazić 1/3 w zmiennoprzecinkowym IEEE lub dziesiętnie. Żaden nie może tego zrobić dokładnie. To wykracza poza odpowiedź na twoje pytanie, ale z powodzeniem zastosowałem tę praktyczną zasadę:

• Przechowuj wartości wprowadzone przez użytkownika w postaci dziesiętnej (ponieważ prawie na pewno wprowadzili je w postaci dziesiętnej – bardzo niewielu użytkowników użyje binarnego lub szesnastkowego). W ten sposób zawsze masz dokładną reprezentację wprowadzoną przez użytkownika.
• Jeśli musisz przechowywać ułamki wprowadzone przez użytkownika, zapisz licznik i mianownik (również w postaci dziesiętnej).
• Jeśli masz system z wieloma jednostkami miary dla tej samej wielkości (np. stopnie Celsjusza / Fahrenheita), a użytkownik może wprowadzić oba, zapisać wprowadzoną wartość i jednostki, w których je wprowadził. Nie próbuj konwertować i zapisywać jako pojedynczej reprezentacji, chyba że możesz to zrobić bez utraty precyzji / dokładności. Używaj przechowywanych wartości i jednostek we wszystkich obliczeniach.
• Przechowuj wartości wygenerowane maszynowo w zmiennoprzecinkowych IEEE (mogą to być liczby wygenerowane przez elektroniczne urządzenie pomiarowe, takie jak czujnik analogowy z przetwornikiem A / D lub niezaokrąglony wynik obliczeń). Pamiętaj, że nie ma to zastosowania, jeśli odczytujesz czujnik przez połączenie szeregowe i już daje wartość w formacie dziesiętnym (np. 18,2 C).
• Przechowuj sumy widoczne dla użytkownika itp. w postaci dziesiętnej (jak konto bankowe saldo). Zaokrąglij odpowiednio, ale użyj tej wartości jako ostatecznej wartości dla wszystkich przyszłych obliczeń.

Komentarze

• Dodałbym: rozważ użycie pakiet matematyczny o dowolnej precyzji, taki jak ARPREC lub decNumber.
• Nie ' t dziesiętne (w przeciwieństwie do binarnych) ma wiele zalet w przypadku wartości całkowitych, takich jak licznik i mianownik ułamka. Każda z nich może przechowywać dokładne wartości całkowite, a system binarny jest bardziej wydajny. ' wiąże się z pewnym kosztem konwersji w obie strony na dane wejściowe i wyjściowe, ale ' prawdopodobnie zostanie obciążony kosztem fizycznego wykonywanie I / O.

Wydaje się, że do tej pory nie wspomniano o koncepcjach niestabilnego algorytmu i źle uwarunkowany problem . Zajmę się najpierw tym pierwszym, ponieważ wydaje się, że jest to częstsza pułapka dla początkujących numerologów.

Rozważ obliczenie potęg (odwrotności) złotego podziału φ=0.61803…; jednym z możliwych sposobów jest użycie wzoru rekursji φ^n=φ^(n-2)-φ^(n-1), zaczynając od φ^0=1 i φ^1=φ. Jeśli uruchomisz tę rekurencję w swoim ulubionym środowisku obliczeniowym i porównasz wyniki z dokładnie oszacowanymi mocami, zobaczysz powolną erozję cyfr znaczących. 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} 

Rzekomy wynik dla φ^41 ma nieprawidłowy znak, a nawet wcześniej obliczone i rzeczywiste wartości φ^39 nie mają wspólnych cyfr (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Algorytm jest zatem niestabilny i nie należy używać tej formuły rekursji w niedokładnej arytmetyce. Jest to spowodowane nieodłączna natura formuły rekursji: istnieje „rozkładające się” i „rosnące” rozwiązanie tej rekursji, a próba obliczenia „zanikającego” rozwiązania za pomocą rozwiązania naprzód, gdy istnieje alternatywne „rosnące” rozwiązanie, błaga o numeryczny żal. Należy zatem upewnić się, że jego / jej algorytmy numeryczne są stabilne.

A teraz przejdźmy do koncepcji źle uwarunkowanego problemu: nawet jeśli może istnieć stabilny sposób coś numerycznie, może być bardzo dobrze, że masz problem po prostu nie mogą być rozwiązane przez twój algorytm. To wina samego problemu, a nie metody rozwiązania. Kanonicznym przykładem w numeryce jest rozwiązanie równań liniowych obejmujących tak zwaną „macierz Hilberta”:

macierz jest kanonicznym przykładem macierzy źle uwarunkowanej : próba rozwiązania układu z dużą macierzą Hilberta może zwrócić niedokładne rozwiązanie.

Tutaj „sa Mathematica demonstracja: 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ładnej arytmetyki

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 uwarunkowania).

W obu przypadkach po prostu zwiększ precyzja nie jest lekarstwem; opóźni tylko nieuchronną erozję liczb.

Oto, z czym możesz się spotkać. Rozwiązania mogą być trudne: po pierwsze, albo wrócisz do deski kreślarskiej, albo przeczesujesz czasopisma / książki / cokolwiek, aby znaleźć, jeśli ktoś inny wymyślił lepsze rozwiązanie niż ty; po drugie, poddaj się albo przeformułuj swój problem na coś łatwiejszego do rozwiązania.

Zostawię ci cytat z Dianne O „Leary:

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

ponieważ dziesiętnych liczb o podstawie 10 nie można wyrazić za pomocą podstawy 2

lub innymi słowy 1/10 nie można przekształcone w ułamek z potęgą 2 w mianowniku (czyli tym w istocie są liczby zmiennoprzecinkowe)

Komentarze

• Niezupełnie prawdziwe: 0,5 a 0,25 można wyrazić w podstawie 2. Myślę, że masz na myśli ” nie wszystkie liczby dziesiętne o podstawie 10 „.
• Dokładniej. Nie wszystkie liczby ułamkowe można dokładnie przedstawić za pomocą notacji zmiennoprzecinkowej (tj. Za pomocą. Zarówno podstawa 2, jak i podstawa 10 mają dokładnie ten problem). Spróbuj 9*3.3333333 dziesiętnie i porównaj to z 9*3 1/3
• To jest najczęstsze źródło liczb zmiennoprzecinkowych dezorientacja. .1 + .1 != .2 ponieważ używane jest zmiennoprzecinkowe kodowanie binarne, a nie dziesiętne.
• @SeanMcMillan: I 1.0/3.0*3.0 != 1.0, ponieważ zmiennoprzecinkowe -punktowe kodowanie binarne jest używane, a nie trójargumentowe.

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 przedstawić 1/3, czyli 1/100. Okazuje się, że z wielu praktycznych powodów nie jest to zbyt przydatne. Jest jeden duży wyjątek: w finansach często pojawiają się ułamki dziesiętne. Dzieje się tak głównie dlatego, że finanse są zasadniczo ludzką, a nie fizyczną działalnością.

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

Komentarze

• Co gorsza, podczas gdy nieskończona (policzalnie nieskończona) ilość pamięci umożliwiłaby reprezentowanie wszystkich racjonalnych, nie wystarczy do przedstawienia liczb rzeczywistych. Co gorsza, prawie wszystkie liczby rzeczywiste nie są liczbami obliczalnymi. Najlepsze, co możemy zrobić przy ograniczonej ilości pamięci, to przybliżyć podzbiór liczb rzeczywistych o skończonym zakresie.
• @Kevin: Ty ' mówisz o obliczalnych liczbach, które są niewielkim podzbiorem (podzbiorem z miarą zero) liczb rzeczywistych.
• +1 dla najbardziej podstawowe wyjaśnienie: ' próbujesz przedstawić nieskończoną liczbę liczb o skończonej liczbie bitów.
• @DavidHammen: Liczby obliczalne to niewielki podzbiór ( miary zero) liczb rzeczywistych – ale każda liczba, z którą ' kiedykolwiek będziesz pracować w programie, jest z definicji obliczalna.
• @Giorgio: If wybierzesz właściwą reprezentację, pierwiastek kwadratowy z 2 jest reprezentowany, na przykład jako ciąg "√2". (Mój stary kalkulator HP-48 był w stanie dokładnie to zrobić, a podniesienie tej wartości do kwadratu dało dokładnie 2.0.) Istnieje tylko policzalna nieskończoność możliwych do przedstawienia liczb rzeczywistych dla skończona reprezentacja – ale żadne obliczenia nie mogą dać liczby, która w zasadzie nie jest reprezentowalna. W praktyce binarne liczby zmiennoprzecinkowe drastycznie ograniczają zbiór liczb, które można przedstawić, z korzyścią w postaci niesamowitej szybkości i niewielkiej ilości miejsca w porównaniu do reprezentacji symbolicznych.

jedyny naprawdę oczywisty problem z zaokrąglaniem liczb zmiennoprzecinkowych, o którym myślę, dotyczy filtrów średniej ruchomej:

$$ \ begin {align} y [n] & = \ frac {1} {N} \ sum \ limits_ {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 szumu, chcesz mieć pewność, że $ x [n] $, które dodasz w bieżących próbkach, jest dokładnie takie samo jak $ x [nN] $, które odejmiesz $ N $ próbek w przyszłości. jeśli tak nie jest, to co innego to mały śmieć, który utknie w twojej linii opóźnienia i nigdy nie wyjdzie. Dzieje się tak 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 w środku. ale jest to integrator i wszelkie bzdury, które zostaną zintegrowane i nie zostaną całkowicie usunięte, będą istnieć w sumie integratora na zawsze. W tym miejscu wartości stałoprzecinkowe nie mają tego samego problemu, co liczby zmiennoprzecinkowe.

Komentarze

• hej, czy ' t $ LaTeX $ math znaczniki działają na forum prog.SE ??? że ' jest naprawdę kiepski, jeśli nie ' t.
• Patrz to na meta.SO i połączone pytania