Co způsobuje chyby zaokrouhlování s plovoucí desetinnou čárkou?

Je to proto, že některé zlomky potřebují vyjádřit velmi velké (nebo dokonce nekonečné) množství míst bez zaokrouhlování. To platí pro desetinnou notaci stejně jako pro binární nebo jakoukoli jinou. Pokud byste omezili počet desetinných míst, které se mají použít pro vaše výpočty (a vyhněte se provádění výpočtů ve zlomkové notaci), museli byste zaokrouhlit i jednoduchý výraz jako 1/3 + 1/3. Místo toho, abyste ve výsledku psali 2/3, byste museli napsat 0,3333 + 0,33333 = 0,66666, což není totožné s 2/3.

V případě počítače je počet číslic omezen technickou podstatou svých registrů paměti a CPU. Interně použitá binární notace přidává další obtíže. Počítače obvykle nemohou „vyjadřovat čísla ve zlomkové notaci, ačkoli některé programovací jazyky tuto schopnost přidávají, což umožňuje do určité míry se těmto problémům vyhnout.

Co by měl každý počítačový vědec vědět o aritmetice s plovoucí desetinnou čárkou

Komentáře

• Spot on. Ale také bych si všiml, že některá čísla, která končit v desítkové soustavě ‚ t končit v binární podobě. Zejména 0,1 je opakující se číslo v binární podobě, takže žádné binární číslo s plovoucí desetinnou čárkou nemůže přesně představovat 0,1.
• Plovoucí body nejsou ‚ užitečné pouze pro mnoho desetinných míst. 32bitová celá čísla mohou počítat až asi 4 miliardy, ale 32bitový float může být téměř nekonečně velký.
• Zlomky, které můžeme vyjádřit jako konečná desetinná místa, jsou zejména ty, jejichž jmenovatelé ‚ primární faktorizace obsahuje pouze 2 a 5 (např. můžeme vyjádřit 3/10 a 7/25 , ale ne 11/18). Když přejdeme na binární, ztratíme faktor 5, takže lze přesně vyjádřit pouze dyadické racionály (např. 1/4, 3/128).

Zaokrouhlovací chyby vycházejí především ze skutečnosti, že nekonečno všech reálných čísel nemůže být reprezentován konečnou pamětí počítače , natož malý kousek paměti, jako je jedna proměnná s plovoucí desetinnou čárkou , takže mnoho uložených čísel je jen přibližné hodnoty čísla, které mají představovat.

Protože existuje pouze omezený počet hodnot, které nejsou aproximace a každá operace mezi aproximací a jiným číslem vede k aproximaci, chyby zaokrouhlování jsou téměř nevyhnutelné .

Důležité je uvědomit si, kdy je pravděpodobné, že způsobí problém a podniknout kroky ke zmírnění rizik .

Kromě David Goldberg je základní co každý počítačový vědec Měli byste vědět o aritmetice s plovoucí desetinnou čárkou (znovu publikováno společností Sun / Oracle jako příloha k jejich Numerickému Průvodce výpočty ), o kterém se zmínil thorsten , ACCU deník přetížení publikoval vynikající sérii článků od Richarda Harrisa o Floating Point Blues .

Série začala

• Budeš muset přemýšlet! v Přetížení # 99 ( pdf , p5-10):

Numerical co mputing má mnoho úskalí. Richard Harris začíná hledat stříbrnou kulku.

Drak numerické chyby není často probuzen z jeho spánku, ale bude-li k němu přistupován obezřetně, způsobí neopatrným programátorským výpočtům občas katastrofické škody.

Tolik, že někteří programátoři, kteří na něj narazili v lesích aritmetiky s plovoucí desetinnou čárkou IEEE 754, doporučují svým kolegům, aby necestovali po této férové zemi.

V této sérii článků prozkoumáme svět numerických výpočtů, kontrastní aritmetika s plovoucí desetinnou čárkou s některými technikami, které byly navrženy jako bezpečnější náhrady. Dozvíme se, že území draka je opravdu dalekosáhlé a že obecně musíme opatrně šlapat, pokud se bojíme jeho zničující pozornost.

Richard začíná vysvětlením taxonomie reálných čísel, racionálních, iracionálních, algebraických a transcendentálních. Poté pokračuje vysvětlením reprezentace IEEE754, než přejde k chybě zrušení a pořadí problémů s prováděním.

Pokud nečtete hlouběji než toto, budete mít vynikající základy v problémech spojených s čísly s plovoucí desetinnou čárkou .

Pokud se však chcete dozvědět více, pokračuje s

• Proč Fixed Point Won“ t Cure Your Floating Point Blues in Přetížení č. 100 ( pdf , p15-22)
• Proč Rationals nebude Vyléčte své Blues s plovoucí desetinnou čárkou v Přetížení # 101 ( pdf , p9-13)
• Proč počítačová algebra nevyléčí vaše plovoucí body Blues v přetížení # 102 ( pdf , p9- 14).
• Proč intervalová aritmetika nevyléčí váš pohyblivý bod Blues in Přetížení 103 ( pdf , p19-24)

Poté přepne na pokus o pomoc s léčením Calculus Blues

• Proč [zde vložte algoritmus] váš Calculus Blues nevyléčí in Přetížení 104 ( pdf , s. 22-24).
• Proč konečné rozdíly nevyléčí váš Calculus Blues in Přetížení 105 ( pdf , p5-12).
• Proč Polynomiální aproximace nevyléčí váš Calculus Blues in Přetížení 106 ( pdf , p16-25).
• Proč počítačová algebra nevyléčí váš Calculus Blues v Přetížení 107 ( pdf , str. 15-20).

a v neposlední řadě existuje

• Proč automatická diferenciace váš Calculus Blues nevyléčí v Přetížení 108 ( pdf , str.4-11).

Celá řada článků je stojí za to se na ně podívat a celkem na 66 stránkách jsou stále menší než 77 stránek Goldbergovy práce .

I když to Série pokrývá většinu stejného terénu, shledal jsem ji spíše přístupnější než Goldbergův papír . Zjistil jsem také, že je snazší porozumět složitějším částem článku po přečtení dřívějších článků o Richardsovi a po těchto raných článcích se Richard rozvětvuje do mnoha zajímavých oblastí, kterých se Goldbergova práce nedotkla.

As takto hovoří ak zmíněno v komentářích:

Jako autor ty články, které bych rád zmínil, že jsem vytvořil jejich interaktivní verze na svém blogu www.thusspakeak.com počínaje protospakeak.com/ak/2013/06 .

Komentáře

• Jako autor těchto článků bych rád ‚ zmínil, že jsem na svém blogu www.thusspakeak.com vytvořil jejich interaktivní verze počínaje protospakeak.com/ak/2013/06 .
• děkuji @ protospakea.k. Přidal jsem ‚ poznámku na mou odpověď, a tho interaktivní prvky fungují velmi dobře.

No, thorsten má definitivní odkaz . Přidal bych:

Jakákoli forma reprezentace bude mít u nějakého čísla nějakou chybu zaokrouhlování. Zkuste vyjádřit 1/3 v IEEE s plovoucí desetinnou čárkou nebo v desítkové soustavě. Ani jeden to nedokáže přesně. To jde nad rámec odpovědi na vaši otázku, ale úspěšně jsem použil toto pravidlo:

• Ukládejte uživatelem zadané hodnoty v desítkové soustavě (protože je téměř jistě zadali v desítkové reprezentaci – velmi málo uživatelů použije binární nebo hex). Tímto způsobem máte vždy přesnou reprezentaci zadanou uživatelem.
• Pokud musíte ukládat zlomky zadané uživatelem, ukládejte čitatele a jmenovatele (také v desítkové soustavě)
• Pokud máte systém s více měrnými jednotkami pro stejné množství (jako Celsius / Fahrenheit) a uživatel může zadat obojí, uložit hodnotu, kterou zadal, a jednotky, do kterých je zadal. Nepokoušejte se převést a uložit jako jednu reprezentaci, pokud to nezvládnete bez ztráty přesnosti / přesnosti. U všech výpočtů použijte jednotky a uložené hodnoty.
• Ukládejte strojem generované hodnoty do plovoucí desetinné čárky IEEE (mohou to být čísla generovaná elektronickým měřicím zařízením, jako je analogový snímač s A / D převodníkem, nebo nezaokrouhlený výsledek výpočtu). Všimněte si, že to neplatí, pokud čtete snímač přes sériové připojení a již to dává hodnotu v desítkovém formátu (např. 18,2 ° C).
• Ukládejte součty, které lze zobrazit, atd., v desítkovém formátu (jako bankovní účet) Zůstatek). Vhodně zaokrouhlete, ale tuto hodnotu použijte jako definitivní hodnotu pro všechny budoucí výpočty.

Komentáře

• Chtěl bych přidat: Zvažte použití matematický balíček s libovolnou přesností, jako je ARPREC nebo decNumber.
• Nemám ‚ t desítkové číslo (na rozdíl od binárního) má mnoho výhod pro celočíselné hodnoty, jako je čitatel a jmenovatel zlomku. Buď můžete uložit přesné celočíselné hodnoty, a binární je efektivnější. ‚ jsou určité náklady na převod tam a zpět pro vstup a výstup, ale ‚ je pravděpodobné, že budou zaplaveny náklady na fyzickou provádění I / O.

Zdá se, že dosud nebyly zmíněny koncepty nestabilního algoritmu a špatně podmíněný problém . Nejprve se budu zabývat tím prvním, protože to se zdá být častějším úskalím pro začínající numeriky.

Zvažte výpočet pravomocí (vzájemného) zlatého řezu φ=0.61803…; jedním z možných způsobů, jak toho dosáhnout, je použít vzorec rekurze φ^n=φ^(n-2)-φ^(n-1) počínaje φ^0=1 a φ^1=φ. Pokud spustíte tuto rekurzi ve svém oblíbeném výpočetním prostředí a porovnáte výsledky s přesně vyhodnocenými schopnostmi, zjistíte pomalou erozi významných čísel. Tady je to, co se stane například v 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} 

Údajný výsledek pro φ^41 má nesprávné znaménko a ještě dříve vypočítané a skutečné hodnoty pro φ^39 nesdílejí žádné společné číslice (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Algoritmus je tedy nestabilní a tento rekurzní vzorec by se neměl používat v nepřesné aritmetice. Je to kvůli inherentní povaha rekurzního vzorce: existuje „rozpadající se“ a „rostoucí“ řešení této rekurze a pokus o výpočet „rozpadajícího se“ řešení pomocí dopředného řešení, když existuje alternativní „rostoucí“ řešení, prosí o numerický zármutek. Měli bychom tedy zajistit, aby jeho numerické algoritmy byly stabilní.

Nyní k konceptu špatně podmíněného problému: i když může existovat stabilní způsob, jak to udělat něco číselně, může se velmi dobře stát, že problém, který máte Váš algoritmus prostě nemůže být vyřešen. To je chyba samotného problému, a ne metody řešení. Kanonickým příkladem v numerice je řešení lineárních rovnic zahrnujících tzv. „Hilbertovu matici“:

matice je kanonickým příkladem špatně podmíněné matice: pokus o řešení systému s velkou Hilbertovou maticí může vrátit nepřesné řešení.

Zde „sa Mathematica demonstrace: porovnejte výsledky přesné aritmetiky

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}} 

a nepřesné aritmetiky

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}} 

(Pokud jste to vyzkoušeli v Mathematica , všimnete si několika chybových zpráv varujících před zobrazením špatného stavu.)

V obou případech jednoduše zvětšíte přesnost není lékem; jen to oddálí nevyhnutelnou erozi čísel.

S tím byste se mohli setkat. Řešení mohou být obtížná: zaprvé, buď se vrátíte na rýsovací prkno, nebo se budete procházet deníky / knihami / čímkoli, abyste zjistili, zda někdo jiný přišel s lepším řešením, než máte vy; za druhé se buď vzdáte, nebo přeformulujete svůj problém na něco přitažlivějšího.

Nechám vás s citátem od Dianne O „Leary:

Život nás může potkat s některými špatně podmíněnými problémy, ale není dobrý důvod spokojit se s nestabilním algoritmem.

protože základ 10 desetinných čísel nelze vyjádřit v základu 2

nebo jinými slovy 1/10 nelze transformována na zlomek se silou 2 ve jmenovateli (což jsou v podstatě čísla s plovoucí desetinnou čárkou)

Komentáře

• Není to úplně pravda: 0,5 a 0,25 lze vyjádřit v základně 2. Myslím, že máte na mysli “ ne všechna desetinná čísla základny 10 „.
• Přesněji. Ne všechna zlomková čísla lze přesně vyjádřit pomocí zápisu s plovoucí desetinnou čárkou (tj. S. Jak základna 2, tak základna 10 mají tento přesný problém). Zkuste 9*3.3333333 v desítkové soustavě a srovnejte jej s 9*3 1/3
• Toto je nejběžnější zdroj s plovoucí desetinnou čárkou zmatek. .1 + .1 != .2 protože se používá binární kódování s plovoucí desetinnou čárkou, nikoli desítkové.
• @SeanMcMillan: A 1.0/3.0*3.0 != 1.0, protože plovoucí -bodové binární kódování se používá, nikoli trinární.

V matematice je nekonečně mnoho racionálních čísel . 32bitová proměnná může mít pouze 2 ³² různé hodnoty a 64bitová proměnná pouze 2 ⁶⁴ hodnoty. Proto existuje nekonečně mnoho racionálních čísel, která nemají přesné zastoupení.

Mohli bychom přijít se schématy, která by nám umožnila dokonale reprezentovat 1/3 nebo 1/100. Ukazuje se, že z mnoha praktických důvodů to není velmi užitečné. Existuje jedna velká výjimka: ve financích se často objevují desetinné zlomky. Je tomu tak hlavně proto, že finance jsou v zásadě lidská činnost, nikoli fyzická.

Proto se obvykle rozhodneme použít binární plovoucí desetinnou čárku a zaokrouhlit libovolnou hodnotu, která nemůže být v binárním vyjádření. Ale ve financích někdy volíme desetinnou plovoucí desetinnou čárku a zaokrouhlujeme hodnoty na nejbližší desetinnou hodnotu .

Komentáře

• Ještě horší je, že zatímco nekonečné (spočetně nekonečné) množství paměti by člověku umožnilo reprezentovat všechny racionály, nebylo by postačující pro reprezentaci realit. Ještě horší je, že téměř všechna reálná čísla nejsou vypočítatelná čísla. Nejlepší, co můžeme udělat s konečným množstvím paměti, je přiblížit podmnožinu konečných rozsahů real.
• @Kevin: ‚ Mluvíte o vypočítatelných číslech, což je malá podmnožina realit. (Podmnožina s mírou nula).
• +1 pro nejzákladnější vysvětlení: ‚ Snažíte se představovat nekonečné množství čísel s konečným počtem bitů.
• @DavidHammen: Vyčíslitelná čísla jsou malou podmnožinou ( nula) realit – ale každé číslo, se kterým ‚ kdy v programu budete pracovat, je podle definice vypočítatelné.
• @Giorgio: If vyberete správné znázornění, druhá odmocnina 2 je reprezentovatelná, například jako řetězec "√2". (Moje stará kalkulačka HP-48 to dokázala přesně a kvadratura této hodnoty vedla k přesně 2.0.) Pro libovolné existuje pouze spočetné nekonečno reprezentovatelných reálných čísel konečná reprezentace – ale žádný výpočet nemůže přinést číslo, které není v zásadě reprezentovatelné. V praxi binární plovoucí desetinná čárka drasticky omezuje množinu reprezentovatelných čísel, s výhodou bleskové rychlosti a malého úložiště ve srovnání se symbolickými reprezentacemi.

jediný skutečně zjevný „problém zaokrouhlování“ s čísly s plovoucí desetinnou čárkou, o kterém si myslím, je s filtry klouzavého průměru:

$$ \ 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 fungovalo bez hromadění hluku, chcete se ujistit, že $ x [n] $, které přidáte do aktuálních vzorků, je přesně stejné jako $ x [nN] $, které odečtete $ N $ vzorky do budoucnosti. pokud tomu tak není, pak se liší trochu hovno, které se zasekne ve vaší zpožďovací linii a nikdy nevyjde. to je proto, že tento filtr s klouzavým průměrem je ve skutečnosti vytvořen s IIR, který má okrajově stabilní pól na $ z = 1 $ a nulu, která jej ruší uvnitř. ale je to integrátor a všechny kecy, které se integrují a nebudou zcela odstraněny, budou v integračním součtu navždy existovat. to je místo, kde pevný bod nemá stejný problém jako čísla s plovoucí desetinnou čárkou.

Komentáře

• hej, ‚ t $ LaTeX $ math markup nefunguje ve fóru prog.SE ??? that ‚ s opravdu chromý, pokud to není ‚ t.
• Viz to na meta.SO a související otázky