Mi okozza a lebegőpontos kerekítési hibákat?

Ennek oka, hogy egyes frakcióknak nagyon nagy (vagy akár végtelen) mennyiségű helyre van szükségük, hogy kerekítés nélkül kifejezhessék őket. Ez ugyanúgy igaz a tizedes jelölésre, mint a binárisra vagy bármely másra. Ha korlátozná a számításokhoz használandó tizedesjegyek számát (és elkerülné a számítások törtrészes jelölését), akkor még egy egyszerű kifejezést is 1/3 + 1/3 értékkel kell kerekítenie. Ahelyett, hogy 2/3-ot írna, ennek eredményeként 0.33333 + 0.33333 = 0.66666 értéket kell írnia, ami nem azonos a 2/3-val. memóriája és CPU regiszterei. A belsőleg használt bináris jelölés további nehézségekkel jár. A számítógépek általában nem képesek számokat frakcionális jelöléssel kifejezni, bár egyes programozási nyelvek hozzáadják ezt a képességet, ami lehetővé teszi bizonyos problémák elkerülését.

Amit minden informatikusnak tudnia kell a lebegőpontos számtanról

Megjegyzések

• Helyezzen el. De azt is megjegyezném, hogy néhány szám, tizedesvesszővel végződik don ‘ t binárisan végződik. Különösen a 0,1 bináris számban ismétlődő szám, így egyetlen lebegőpontos bináris szám sem reprezentálhat pontosan 0,1-et.
• Lebegő A pontok nem ‘ t sok tizedesjegyig használhatók. A 32 bites egészek csak körülbelül 4 milliárdot számlálhatnak, de a 32 bites úszó szinte végtelenül nagy lehet.
• Különösen azok a törtek, amelyeket véges tizedesjegyekkel kifejezhetünk, azok, amelyek nevezői ‘ elsődleges faktorizáció csak 2-t és 5-öt tartalmaz (pl. 3/10 és 7/25 kifejezhetünk) , de nem 11/18). Amikor binárisra lépünk, elveszítjük az 5-ös tényezőt, így csak a diádikus racionálist (pl. 1/4, 3/128) lehet pontosan kifejezni.

A kerekítési hibák elsősorban abból fakadnak, hogy az összes valós szám végtelen nem ábrázolható a számítógép véges memóriájával , nem is beszélve egy apró memóriaszeletről, például egyetlen lebegőpontos változó ról, ezért sok tárolt szám csak azoknak a számoknak a közelítése, amelyeket képviselniük kell.

Mivel csak korlátozott számú érték van, amelyek nem egy közelítés, és a közelítés és egy másik szám közötti bármilyen művelet közelítést eredményez, a kerekítési hibák szinte elkerülhetetlenek .

A fontosak rá kell jönni, hogy mikor okoznak problémát , és tegyen lépéseket a kockázatok enyhítésére .

A David Goldberg “elengedhetetlen Mit minden számítógépes tudós t Tudnia kell a lebegőpontos aritmetikáról (a Sun / Oracle által újrakiadva numerikus mellékletükként Számítási útmutató ), amelyet thorsten , a ACCU napló Túlterhelés kiváló cikk-sorozatot adott Richard Harris a Lebegőpontos blues .

A sorozat a következővel kezdődött:

• Gondolkodnod kell! itt: Túlterhelés # 99 ( pdf , 5-10. o.):

Numerikus társ Az mputálásnak sok buktatója van. Richard Harris ezüst golyót kezd keresni.

A numerikus hibák sárkányát nem gyakran ébresztik el alvásából, de ha óvatlanul közeledik, időnként katasztrofális károkat okoz az óvatlan programozó számításainak.

Olyannyira, hogy néhány programozó, miután az IEEE 754 lebegőpontos aritmetikájának erdeiben rákezdett, azt tanácsolja társainak, hogy ne utazzanak azon a tisztességes földön.

Ebben a cikksorozatban feltárjuk a numerikus számítás világa, szembeállítva a lebegőpontos aritmetikát néhány olyan technikával, amelyet biztonságosabb helyettesítőként javasoltak. Meg fogjuk tudni, hogy a sárkány területe valóban messze van, és hogy általában óvatosan kell taposnunk, ha félünk tőle pusztító figyelem.

Richard a valós számok taxonómiájának magyarázatával kezdi, racionális, irracionális, algebrai és transzcendentális. Ezután elmagyarázza az IEEE754 reprezentációt, mielőtt a törlési hibákkal és a végrehajtás sorrendjével foglalkozna.

Ha ennél mélyebben nem olvas, akkor kiválóan megalapozza a lebegőpontos számokkal kapcsolatos problémákat. .

Ha azonban többet szeretne tudni, folytatja a következőt:

• Miért nem gyógyítja meg a fixpont a lebegőpontos kékeket a Túlterhelés # 100 ( pdf , 15–22. o.)
• Miért nem fognak racionálisak lenni? Gyógyítsa meg a lebegőpontos kékeket a 101-es túlterheléssel ( pdf , p9-13)
• Miért nem gyógyítja meg a számítógépes algebra a lebegőpontos kékeket a túlterhelésben # 102 ( pdf , p9- 14).
• Miért nem gyógyítja meg az intervallumszámolás a lebegőpontos kékeket a 103-as túlterheléssel ( pdf , 19–24. o.)

Ezután átáll arra, hogy segítsen gyógyítani a Kalkulusokat

ul>

és nem utolsó sorban létezik

• Miért nem gyógyítja meg az automatikus differenciálódás a kalkulus kékeket 108-ban túlterhelés ( pdf , 4–11. oldal).

A teljes cikksorozat érdemes megnézni, és összesen 66 oldal, még mindig kisebbek, mint a Goldberg-lap 77 oldala.

Bár ez sorozat nagyrészt ugyanazt a terepet fedi le, inkább hozzáférhetőnek találtam, mint Goldberg “s papírja . A cikk bonyolultabb részeinek megértését is megkönnyítettem, miután elolvastam a korábbi Richards-cikkeket, és ezek után a korai cikkek után Richard számos érdekes területre ágazik le, amelyeket nem érint a Goldberg-papír.

Ahogy így ak beszélt a megjegyzésekben:

A azokat a cikkeket szeretném megemlíteni, hogy interaktív változatokat hoztam létre a blogomban www.thusspakeak.com thusspakeak.com/ak/2013/06 .

Megjegyzések

• E cikkek szerzőjeként ‘ szeretném megemlíteni, hogy interaktív változatokat hoztam létre a www.thusspakeak.com blogomban thusspakeak.com/ak/2013/06 .
• Köszönöm @ thusspakea.k. Én ‘ megjegyzést fűztem válaszomra, és tho Az interaktív elemek nagyon szépen működnek.

Nos, thorsten rendelkezik a végleges linkkel . Hozzáteszem:

A reprezentáció bármelyik formájánál kerekítési hiba lép fel bizonyos számoknál. Próbáld kifejezni az 1/3-at IEEE lebegőponttal vagy tizedesjegyekkel. Egyik sem tudja pontosan megtenni. Ez túlmutat a kérdés megválaszolásán, de ezt az ökölszabályt sikeresen alkalmaztam:

• A felhasználó által megadott értékeket tizedesszerűen tárolja (mert szinte biztosan tizedes formában adták meg – nagyon kevés felhasználó bináris vagy hexa értéket fog használni. Így mindig pontosan megadhatja a felhasználó által megadott ábrázolást.
• Ha a felhasználó által megadott törtrészeket kell tárolnia, akkor tárolja a számlálót és a nevezőt (tizedesben is)
• Ha rendelkezik rendszer több mértékegységgel ugyanarra a mennyiségre (például Celsius / Fahrenheit), és a felhasználó mindkettőt megadhatja, eltárolhatja a megadott értéket és az egységeket, amelyekbe beírta őket. Ne próbálja konvertálni és menteni egyetlen ábrázolásként, hacsak nem tudja megtenni a pontosság / pontosság elvesztése nélkül. Az összes számítás során használja a tárolt érték és egységeket.
• Tárolja a gép által létrehozott értékeket az IEEE lebegőpontjában (ez lehet számok generálása elektronikus mérőeszköz, például analóg érzékelő A / D átalakítóval, vagy a számítás nem kerekített eredménye). Ne feledje, hogy ez nem érvényes, ha egy érzékelőt soros kapcsolaton keresztül olvas és már ad tizedes formátumban adja meg az értéket (pl. 18,2 C).
• A felhasználó által megtekinthető összegeket stb. tizedesjegyben tárolja (például bankszámla) egyensúly). Megfelelően kerekítsen, de ezt az értéket használja a végső értékként minden jövőbeli számításhoz.

Megjegyzések

• Hozzáteszem: Fontolja meg egy tetszőleges pontosságú matematikai csomag, például ARPREC vagy decNumber.
• Nem adok ‘ t decimális értéket (szemben a bináris értékkel) sok előnye van az egész értékeknek, például a számlálónak és egy tört nevezője. Bármelyik pontos pontos értékeket tárolhat, és a bináris hatékonyabb. ‘ némi költsége van a be- és kimenet oda-vissza konvertálásának, de ezt ‘ valószínűleg a fizikai terhelés fogja elárasztani. az I / O végrehajtása.

Amit úgy tűnik, hogy eddig nem említettünk, azok egy instabil algoritmus fogalmai és egy rossz feltételű probléma . Először az előbbivel foglalkozom, mivel ez a kezdő numerikusok számára gyakoribb buktatónak tűnik.

Vizsgáljuk meg a (kölcsönös) aranyképesség φ=0.61803…; ennek egyik lehetséges módja a φ^n=φ^(n-2)-φ^(n-1) rekurziós képlet használata, kezdve φ^0=1 és φ^1=φ. Ha ezt a rekurziót futtatja kedvenc számítógépes környezetében, és összehasonlítja az eredményeket a pontosan értékelt teljesítményekkel, akkor a számadatok lassú erózióját fogja észlelni. Itt történik például a Mathematica ban:

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} 

A (z) φ^41 hibás előjelű, és még korábban, a φ^39 számított és tényleges értékei nem osztoznak közös számjegyekkel (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Az algoritmus tehát instabil, és nem szabad ezt a rekurziós képletet pontatlan aritmetikában használni. Ennek oka a rekurziós képlet eredendõ jellege: ennek a rekurziónak van “bomló” és “növekvõ” megoldása, és a “bomló” megoldás elõre szóló megoldással történõ kiszámítása, amikor van alternatív “növekvõ” megoldás, a numerikus bánatért könyörög. Biztosítani kell tehát, hogy numerikus algoritmusai stabilak legyenek.

Most pedig folytassuk a feltétel nélküli probléma fogalmát: annak ellenére, hogy lehet erre stabil mód valami numerikusan, nagyon is lehet, hogy a probléma ha Csak nem lehet megoldani az algoritmusoddal. Ez maga a probléma hibája, és nem a megoldási módszer. A numerikus kanonikus példa az úgynevezett “Hilbert-mátrixot” magában foglaló lineáris egyenletek megoldása:

A a mátrix egy kanonikus példa egy rossz állapotú mátrixra: egy rendszer megoldása egy nagy Hilbert-mátrixszal pontatlan megoldást eredményezhet.

Itt “sa Mathematica bemutatás: a pontos számtan eredményeinek összehasonlítása

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

és a pontatlan számtan

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

(Ha kipróbálta a Mathematica ban, akkor megemlít néhány hibaüzenetet, amely figyelmeztet a rossz állapot megjelenésére.)

Mindkét esetben egyszerűen növelje a a pontosság nem gyógyír; csak késlelteti az alakok elkerülhetetlen erózióját.

Ezzel szembesülhet. A megoldások nehézkesek lehetnek: az első, vagy visszamegy a rajztáblához, vagy folyóiratokban / könyvekben / bármi másban jár, hogy megtalálja, ha valaki jobb megoldással állt elő, mint te; a másodikra: vagy feladja, vagy újrafogalmazza a problémáját valami könnyebben kezelhetővé.

Hagyok egy idézetet Dianne O-tól “Leary:

Az élet felvethet néhány feltétel nélküli problémát, de nincs jó ok arra, hogy instabil algoritmussal elégedjünk meg.

mert a 10-es bázis tízes számai nem fejezhetők ki a 2-es alapban

vagy más szavakkal az 1/10 nem adható meg átalakul a nevezőben 2-es hatványú törtté (ami lényegében a lebegőpontos szám)

Megjegyzések

• Nem éppen igaz: 0,5 és 0,25 kifejezhető a 2-es alapban. Azt hiszem, ” -re gondolsz, nem az összes 10-es alapértelmezett tízes számra “.
• Pontosabban. Nem minden tört számot lehet pontosan ábrázolni lebegőpontos jelöléssel (azaz a. Mind a 2, mind a 10 alapnak van ilyen pontos problémája). Próbálkozzon a következővel: 9*3.3333333 tizedesjegyig, és illessze 9*3 1/3
• Ez a lebegőpont leggyakoribb forrása zavar. .1 + .1 != .2 mert lebegőpontos bináris kódolást használnak, nem tizedesjegyet.
• @SeanMcMillan: És 1.0/3.0*3.0 != 1.0, mert lebegő -pont bináris kódolást használ, nem trináris.

A matematikában végtelen sok racionális szám van . Egy 32 bites változónak csak 2 ³² különböző értéke lehet, a 64 bites változónak pedig csak 2 ⁶⁴ értéke. Ezért végtelen sok racionális szám van, amelyeknek nincs pontos ábrázolása.

Kihozhatnánk olyan sémákat, amelyek lehetővé tennék számunkra az 1/3-os, vagyis 1/100-os tökéletes képviseletet. Kiderült, hogy sok gyakorlati célból ez nem túl hasznos. Van egy nagy kivétel: a pénzügyekben a tizedes törtek gyakran felbukkannak. Ez leginkább azért van, mert a pénzügy lényegében emberi tevékenység, nem fizikai.

Ezért általában úgy döntünk, hogy bináris lebegőpontot használunk, és minden olyan értéket kerekítünk, amely nem ábrázolható bináris formában. De a pénzügyekben néha tizedes lebegőpontos és kerek értékeket választunk a legközelebbi tizedesértékre .

Megjegyzések

• Még rosszabb, hogy míg egy végtelen (számtalanul végtelen) memória lehetővé tenné az összes racionális képviseletét, az nem elegendő a valósok ábrázolásához. Még ennél is rosszabb, hogy a valós számok szinte mindegyike nem kiszámítható szám. A legjobb, amit véges memóriával tehetünk, ha közelítjük a valósok véges tartományának részhalmazát.
• @Kevin: ‘ a kiszámítható számokról beszélsz, amelyek a valósak apró részhalmaza (nulla mértékű részhalmaz).
• +1 a legalapvetőbb magyarázat: ‘ végtelen számú számot próbál véges számú bitet képviselni.
• @DavidHammen: A kiszámolható számok egy apró részhalmaz ( nulla mértéke) a valósokból – de minden szám, amellyel ‘ valaha együtt dolgozol egy programban, definíció szerint kiszámítható.
• @Giorgio: Ha a megfelelő ábrázolást választja, akkor a 2 négyzetgyöke ábrázolható például a "√2" karakterláncként. (A régi HP-48 számológépem pontosan ezt tudta megtenni, és ennek az értéknek a négyzetre emelése pontosan 2.0 eredményt adott.) Csak reprezentálható valós számok számtalan végtelensége van bármelyiknek véges ábrázolás – de semmilyen számítással nem lehet olyan számot adni, amely elvileg nem reprezentálható. A gyakorlatban a bináris lebegőpont drasztikusan korlátozza az ábrázolható számok halmazát, a lángoló sebesség és az apró tárhely előnyeivel a szimbolikus ábrázolásokhoz képest.

az egyetlen igazán nyilvánvaló “kerekítési kérdés” lebegőpontos számokkal szerintem a mozgóátlagos szűrőkkel kapcsolatos:

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

hogy ez anélkül is működjön A zaj felhalmozódása után meg kell győződni arról, hogy az aktuális mintákba felvett $ x [n] $ pontosan megegyezik-e azzal a $ x [nN] $ értékkel, amelyből a $ N $ mintákat kivonja a jövőben. ha nem, akkor a különbség egy kis túró, amely beragad a késleltetési sorodba, és soha nem fog kijönni. ez azért van, mert ez a mozgóátlagos szűrő valójában egy olyan IIR-rel épül fel, amelynek marginálisan stabil pólusa $ z = 1 $ -nál van, és egy nulla, amely megsemmisíti azt belül. de ez egy integrátor, és minden olyan szar, amely integrálódik és nem teljesen távolítható el, az örök időkre az integrátor összegében létezik. Ez az, ahol a fixpontnak nincs ugyanaz a problémája, mint a lebegőpontos számoknak.

Megjegyzések

• hé, nem ‘ t $ LaTeX $ matematikai jelölés működik a prog.SE fórumban ??? hogy ‘ nagyon béna, ha nem ‘ t.
• Lásd: ezt a meta.SO-n és a kapcsolódó kérdésekre