Wat veroorzaakt afrondingsfouten met drijvende komma?

Dit komt doordat sommige breuken een zeer groot (of zelfs oneindig) aantal plaatsen nodig hebben om zonder afronding uit te drukken. Dit geldt zowel voor de decimale notatie als voor binaire of andere. Als u het aantal decimalen dat u voor uw berekeningen wilt gebruiken, zou beperken (en geen berekeningen in breuknotatie zou maken), zou u zelfs een eenvoudige uitdrukking moeten afronden als 1/3 + 1/3. In plaats van 2/3 als resultaat te schrijven, zou je 0.33333 + 0.33333 = 0.66666 moeten schrijven, wat niet identiek is aan 2/3.

In het geval van een computer is het aantal cijfers beperkt door de technische aard van zijn geheugen en CPU-registers. De binaire notatie die intern wordt gebruikt, voegt wat meer problemen toe. Computers kunnen normaal gesproken “geen getallen in breuken uitdrukken, hoewel sommige programmeertalen deze mogelijkheid toevoegen, waardoor deze problemen tot op zekere hoogte kunnen worden vermeden.

Wat elke computerwetenschapper moet weten over drijvende-komma-rekenkunde

Opmerkingen

• Ter plaatse. Maar ik zou ook willen opmerken dat sommige cijfers eindigen in decimaal don ‘ t eindigen in binair getal. In het bijzonder is 0,1 een terugkerend getal in binair en dus kan geen binair getal met drijvende komma exact gelijk zijn aan 0,1.
• Zwevend punten zijn niet ‘ t alleen nuttig voor veel decimalen. 32-bits gehele getallen kunnen slechts tot ongeveer 4 miljard tellen, maar een 32-bits float kan bijna oneindig groot zijn.
• In het bijzonder de breuken die we kunnen uitdrukken als eindige decimalen zijn die waarvan de noemers ‘ priemfactorisatie slechts 2 en 5 bevatten (we kunnen bijvoorbeeld 10 en 25 , maar niet 11/18). Als we naar binair gaan, verliezen we de factor 5, zodat alleen de dyadische rationale getallen (bijv. 1/4, 3/128) exact kunnen worden uitgedrukt.

In de eerste plaats komen afrondingsfouten voort uit het feit dat de oneindigheid van alle reële getallen kan onmogelijk worden weergegeven door het eindige geheugen van een computer , laat staan een klein stukje geheugen zoals een enkele floating point variabele , dus veel opgeslagen getallen zijn slechts benaderingen van het aantal dat ze moeten vertegenwoordigen.

Aangezien er slechts een beperkt aantal waarden is die niet een benadering, en elke bewerking tussen een benadering en een ander getal resulteert in een benadering, afrondingsfouten zijn bijna onvermijdelijk .

De belangrijke ding is om te beseffen wanneer ze waarschijnlijk een probleem zullen veroorzaken en stappen te ondernemen om de risicos te verkleinen .

Naast David Goldberg “s essentiële Wat elke computerwetenschapper t Moet weten over Floating-Point Arithmetic (opnieuw gepubliceerd door Sun / Oracle als een bijlage bij hun Numerieke Computation Guide ), die werd genoemd door thorsten , de ACCU journaal Overbelasting had een uitstekende reeks artikelen van Richard Harris over de Floating Point Blues .

De serie begon met

• Je moet nadenken! in Overload # 99 ( pdf , p5-10):

Numerieke co mputing kent veel valkuilen. Richard Harris gaat op zoek naar een zilveren kogel.

De draak van numerieke fouten wordt niet vaak uit zijn sluimer gewekt, maar als hij onvoorzichtig wordt benaderd, zal hij af en toe catastrofale schade toebrengen aan de berekeningen van de onoplettende programmeur.

Zozeer zelfs dat sommige programmeurs, die hem toevallig tegenkwamen in de bossen van IEEE 754 floating point rekenkunde, hun kameraden afraden om door dat mooie land te reizen.

In deze serie artikelen zullen we onderzoeken de wereld van numeriek computergebruik, waarbij drijvende-kommaberekeningen worden vergeleken met enkele van de technieken die zijn voorgesteld als veiligere vervanging ervan. We zullen leren dat het territorium van de draak inderdaad verreikend is en dat we in het algemeen voorzichtig moeten zijn als we bang zijn voor zijn verwoestende aandacht.

Richard begint met het uitleggen van de taxonomie van reële getallen, rationeel, irrationeel, algebraïsch en transcendentaal. Vervolgens legt hij de IEEE754-weergave uit, voordat hij verder gaat met annuleringsfouten en problemen met de volgorde van uitvoering.

Als je niet dieper leest dan dit, zul je een uitstekende basis hebben voor de problemen die verband houden met getallen met drijvende komma .

Als je echter meer wilt weten, gaat hij verder met

• Waarom Fixed Point niet” uw Floating Point Blues geneest in Overload # 100 ( pdf , p15-22)
• Waarom rantsoenen niet doen Genees uw Floating Point Blues in Overload # 101 ( pdf , p9-13)
• Waarom computeralgebra uw Floating Point Blues niet zal genezen in Overload # 102 ( pdf , p9- 14).
• Waarom intervalberekeningen uw Floating Point Blues niet genezen in Overbelasting 103 ( pdf , p19-24)

Vervolgens schakelt hij over om u te helpen bij het genezen van uw Calculus Blues

• Waarom [voeg algoritme hier in] je calculus blues niet zal genezen in Overbelasting 104 ( pdf , p22-24).
• Waarom eindige verschillen uw calculus blues niet genezen in Overbelasting 105 ( pdf , p5-12).
• Waarom polynomiale benadering niet “geneest uw calculus blues in Overbelasting 106 ( pdf , p16-25).
• Waarom computeralgebra uw calculusblues niet zal genezen in Overload 107 ( pdf , p15-20).

en last but not least is er

• Waarom automatische differentiatie uw Calculus Blues niet geneest in Overbelasting 108 ( pdf , p4-11).

De hele reeks artikelen is het bekijken waard, en met 66 paginas in totaal zijn ze nog steeds kleiner dan de 77 paginas van de Goldberg-paper .

Hoewel dit serie bestrijkt grotendeels hetzelfde terrein, ik vond het eerder toegankelijker dan Goldberg “s paper . Ik vond het ook gemakkelijker om de meer complexe delen van de paper te begrijpen na het lezen van de eerdere Richards-artikelen en na die vroege artikelen vertakt Richard zich in veel interessante gebieden die niet door de Goldberg-paper worden behandeld.

Zoals aldus ak sprak genoemd in opmerkingen:

Als auteur van die artikelen “wil ik graag vermelden dat ik interactieve versies ervan heb gemaakt op mijn blog www.thusspakeak.com beginnend met dusspakeak.com/ak/2013/06 .

Reacties

• Als auteur van die artikelen wil ik ‘ vermelden dat ik interactieve versies ervan heb gemaakt op mijn blog www.thusspakeak.com beginnend met dusspakeak.com/ak/2013/06 .
• Bedankt @dusspakea.k. Ik ‘ heb een opmerking toegevoegd op mijn antwoord, en tho Deze interactieve elementen werken erg goed.

Nou, thorsten heeft de definitieve link . Ik zou willen toevoegen:

Elke vorm van representatie zal een afrondingsfout hebben voor een bepaald getal. Probeer 1/3 uit te drukken in IEEE-drijvende komma, of in decimalen. Geen van beiden kan het nauwkeurig doen. Dit gaat verder dan het beantwoorden van uw vraag, maar ik heb deze vuistregel met succes gebruikt:

• Sla door de gebruiker ingevoerde waarden op in decimalen (omdat ze deze vrijwel zeker in een decimale weergave hebben ingevoerd – zeer weinig gebruikers zal binair of hex gebruiken). Op die manier heb je altijd de exacte door de gebruiker ingevoerde weergave.
• Als je door de gebruiker ingevoerde breuken moet opslaan, sla dan de teller en de noemer op (ook in decimalen).
• Als je een systeem met meerdere maateenheden voor dezelfde hoeveelheid (zoals Celsius / Fahrenheit), en de gebruiker kan beide invoeren, de waarde opslaan die ze hebben ingevoerd en de eenheden waarin ze ze hebben ingevoerd. Probeer niet om te rekenen en op te slaan als een enkele weergave, tenzij je het kunt doen zonder verlies van precisie / nauwkeurigheid. Gebruik de opgeslagen waarde en eenheden in alle berekeningen.
• Bewaar door de machine gegenereerde waarden in IEEE drijvende komma (dit kunnen getallen zijn door een elektronisch meetapparaat, zoals een analoge sensor met een A / D-omzetter, of het niet-afgeronde resultaat van een berekening). Merk op dat dit niet van toepassing is als je een sensor uitleest via een seriële verbinding en deze al geeft u de waarde in een decimaal formaat (bijvoorbeeld 18,2 C).
• Bewaar door gebruikers zichtbare totalen, enz., in decimaal (zoals een bankrekening balans). Rond op de juiste manier af, maar gebruik die waarde als de definitieve waarde voor alle toekomstige berekeningen.

Opmerkingen

• Ik zou willen toevoegen: Overweeg om een rekenpakket met willekeurige precisie, zoals ARPREC of decNumber.
• I don ‘ t decimaal (in tegenstelling tot binair) heeft veel voordeel voor gehele getallen, zoals de teller en noemer van een breuk. Beide kunnen exacte gehele getallen opslaan, en binair is efficiënter. Er zijn ‘ kosten verbonden aan het heen en weer converteren voor invoer en uitvoer, maar die ‘ wordt waarschijnlijk overspoeld door de fysieke kosten van het uitvoeren van de I / O.

Wat tot nu toe niet genoemd lijkt te zijn, zijn de concepten van een onstabiel algoritme en een slecht geconditioneerd probleem . Ik zal eerst de eerste behandelen, aangezien dat een vaker voorkomende valkuil lijkt te zijn voor beginnende numericisten.

Beschouw de berekening van de machten van de (wederkerige) gulden snede φ=0.61803…; een mogelijke manier om dit te doen, is door de recursieformule φ^n=φ^(n-2)-φ^(n-1) te gebruiken, te beginnen met φ^0=1 en φ^1=φ. Als u deze recursie uitvoert in uw favoriete computeromgeving en de resultaten vergelijkt met nauwkeurig geëvalueerde vermogens, zult u een langzame erosie van significante cijfers vinden. Dit is wat er bijvoorbeeld gebeurt in 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} 

Het vermeende resultaat voor φ^41 heeft het verkeerde teken, en zelfs eerder hebben de berekende en werkelijke waarden voor φ^39 geen cijfers gemeen (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Het algoritme is dus onstabiel en je moet deze recursieformule niet gebruiken voor onnauwkeurige rekenkundige bewerkingen. Dit komt door de inherente aard van de recursieformule: er is een ‘rottende’ en ‘groeiende’ oplossing voor deze recursie, en het proberen om de ‘rottende’ oplossing te berekenen door een voorwaartse oplossing wanneer er een alternatieve ‘groeiende’ oplossing is, smeekt om numeriek verdriet. Men moet er dus voor zorgen dat zijn / haar numerieke algoritmen stabiel zijn.

Nu, op het concept van een slecht geconditioneerd probleem: ook al is er misschien een stabiele manier om dit te doen iets numerieks, het kan heel goed zijn dat het probleem u heeft ve kan gewoon niet worden opgelost door uw algoritme. Dit is de fout van het probleem zelf, en niet de oplossingsmethode. Het canonieke voorbeeld in numeriek is de oplossing van lineaire vergelijkingen met de zogenaamde “Hilbert-matrix”:

De matrix is het canonieke voorbeeld van een slecht geconditioneerde matrix: als je probeert een systeem op te lossen met een grote Hilbert-matrix, kan dit een onnauwkeurige oplossing opleveren.

Hier “sa Mathematica demonstratie: vergelijk de resultaten van exacte rekenkunde

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

en onnauwkeurige rekenkunde

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

(Als je het in Mathematica hebt uitgeprobeerd, zul je een paar foutmeldingen opmerken die waarschuwen voor het verschijnen van slechte conditionering.)

In beide gevallen is het eenvoudig om de precisie is geen remedie; het zal alleen de onvermijdelijke erosie van cijfers vertragen.

Dit is waar u mee te maken kunt krijgen. De oplossingen kunnen moeilijk zijn: voor de eerste keer ga je terug naar de tekentafel of doorzoek je tijdschriften / boeken / wat dan ook om te zien of iemand anders een betere oplossing heeft bedacht dan jij; voor de tweede geef je het op, of herformuleer je je probleem tot iets dat meer handelbaar is.

Ik laat je achter met een citaat van Dianne O “Leary:

Het leven kan ons wat slecht geconditioneerde problemen bezorgen, maar er is geen goede reden om genoegen te nemen met een onstabiel algoritme.

omdat decimale getallen met grondtal 10 niet kunnen worden uitgedrukt in grondtal 2

of met andere woorden 1/10 kan niet omgezet in een breuk met een macht van 2 in de noemer (wat drijvende-kommagetallen in essentie zijn)

Opmerkingen

• Niet helemaal waar: 0,5 en 0.25 kan worden uitgedrukt in grondtal 2. Ik denk dat je bedoelt ” niet alle decimale getallen met 10 grondtal “.
• Nauwkeuriger. Niet alle fractionele getallen kunnen exact worden weergegeven met een drijvende-komma-notatie (dwz met de. Zowel grondtal 2 als grondtal 10 hebben dit exacte probleem). Probeer 9*3.3333333 in decimaal en vergelijk het met 9*3 1/3
• Dit is de meest voorkomende bron van drijvende komma verwarring. .1 + .1 != .2 omdat binaire codering met drijvende komma wordt gebruikt, niet decimaal.
• @SeanMcMillan: En 1.0/3.0*3.0 != 1.0, omdat zwevend -punt binaire codering wordt gebruikt, niet trinair.

In de wiskunde zijn er oneindig veel rationale getallen . Een 32-bits variabele kan slechts 2 ³² verschillende waarden hebben en een 64-bits variabele slechts 2 ⁶⁴ waarden. Daarom zijn er oneindig veel rationale getallen die geen nauwkeurige weergave hebben.

We zouden schemas kunnen bedenken waarmee we 1/3 perfect of 1/100 kunnen vertegenwoordigen. Het blijkt dat dit voor veel praktische doeleinden niet erg handig is. Er is één grote uitzondering: in de financiële wereld komen decimale breuken vaak voor. Dat komt vooral omdat financiën in wezen een menselijke activiteit is, niet een fysieke.

Daarom kiezen we er meestal voor om binaire drijvende komma te gebruiken en elke waarde af te ronden die niet in binair kan worden weergegeven. Maar in financiën kiezen we soms decimale drijvende komma en ronden we waarden af op de dichtstbijzijnde decimale waarde .

Opmerkingen

• Erger nog, hoewel een oneindige (aftelbaar oneindige) hoeveelheid geheugen iemand in staat zou stellen om alle rationale getallen te vertegenwoordigen, zou het niet voldoende om de reële getallen weer te geven. Erger nog, bijna alle reële getallen zijn geen berekenbare getallen. Het beste wat we kunnen doen met een eindige hoeveelheid geheugen, is een eindige reeks van de reals te benaderen.
• @Kevin: Je ‘ praat over de berekenbare getallen, wat een kleine subset is (een subset met maat nul) van de reële getallen.
• +1 voor de meest eenvoudige uitleg: je ‘ probeert een oneindig aantal getallen weer te geven met een eindig aantal bits.
• @DavidHammen: berekenbare getallen zijn een kleine subset ( van maat nul) van de reële getallen – maar elk getal waarmee u ‘ ooit zult werken in een programma is per definitie berekenbaar.
• @Giorgio: If u kiest de juiste weergave, de vierkantswortel van 2 is representeerbaar, bijvoorbeeld als de string "√2". (Mijn oude HP-48-rekenmachine was in staat om precies dat te doen, en het kwadrateren van die waarde resulteerde in exact 2.0.) Er is slechts een telbaar oneindig aantal representeerbare reële getallen voor elke eindige representatie – maar geen berekening kan een getal opleveren dat in principe niet representatief is. In de praktijk beperkt binaire drijvende komma de set van representeerbare getallen drastisch, met het voordeel van een enorme snelheid en een kleine opslag in vergelijking met symbolische representaties.

het enige echt voor de hand liggende “afrondingsprobleem” met getallen met drijvende komma waar ik aan denk, is met zwevend gemiddelde filters:

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

om dit te laten werken zonder de opeenhoping van ruis, wilt u er zeker van zijn dat de $ x [n] $ die u in de huidige samples toevoegt, exact hetzelfde is als de $ x [nN] $ die u in de toekomst $ N $ samples zult aftrekken. zo niet, dan is wat anders is een drol die vast komt te zitten in je vertragingslijn en er nooit uit zal komen. dat komt omdat dit voortschrijdend gemiddelde filter eigenlijk is gebouwd met een IIR die een marginaal stabiele pool heeft op $ z = 1 $ en een nul die het binnenin opheft. maar het is een integrator en alle onzin die wordt geïntegreerd en niet volledig wordt verwijderd, zal voor altijd in de som van de integrator bestaan. dit is waar fixed-point niet hetzelfde probleem heeft als drijvende-kommagetallen.

Opmerkingen

• hey, werkt niet ‘ t $ LaTeX $ wiskundige opmaak in het prog.SE-forum ??? dat ‘ is echt zwak als het niet ‘ t.
• Zie dit op meta.SO en gekoppelde vragen