Hvad forårsager afrundingsfejl med flydende punkt?

Dette skyldes, at nogle brøker har brug for en meget stor (eller endda uendelig) mængde steder, der skal udtrykkes uden afrunding. Dette gælder for decimalnotation så meget som for binær eller enhver anden. Hvis du vil begrænse antallet af decimaler, der skal bruges til dine beregninger (og undgå at lave beregninger i brøknotation), bliver du nødt til at afrunde et simpelt udtryk som 1/3 + 1/3. I stedet for at skrive 2/3 som et resultat, skal du skrive 0.33333 + 0.33333 = 0.66666, hvilket ikke er identisk med 2/3.

I tilfælde af en computer er antallet af cifre begrænset af den tekniske natur af dets hukommelse og CPU-registre. Den binære notation, der bruges internt, tilføjer nogle flere vanskeligheder. Computere kan normalt ikke udtrykke tal i fraktionsnotation, selvom nogle programmeringssprog tilføjer denne evne, hvilket gør det muligt at undgå disse problemer i en vis grad.

Hvad enhver computerforsker burde vide om flydende aritmetik

Kommentarer

• Spot on. Men jeg vil også bemærke, at nogle tal, der afsluttes i decimal don ‘ t afsluttes i binær. Især er 0,1 et tilbagevendende tal i binært, så intet flydende punkt binært tal kan nøjagtigt repræsentere 0,1.
• Flydende point er ikke ‘ t er kun nyttige til mange decimaler. 32 bit heltal kan kun tælle op til ca. 4 milliarder, men en 32 bit float kan være næsten uendeligt stor.
• Især er de fraktioner, vi kan udtrykke som endelige decimaler, dem, hvis nævnere ‘ primfaktorisering kun indeholder 2 og 5 (f.eks. kan vi udtrykke 3/10 og 7/25 , men ikke 11/18). Når vi skifter til binær, mister vi faktoren 5, så kun de dyadiske rationelle (f.eks. 1/4, 3/128) kan udtrykkes nøjagtigt.

Afrundingsfejl kommer primært fra det faktum, at uendelighed af alle reelle tal kan umuligt repræsenteres af en computers begrænsede hukommelse , endsige et lille stykke hukommelse, såsom en enkelt variabel med flydende punkt , så mange lagrede numre er bare tilnærmelser til det antal, de skal repræsentere.

Da der kun er et begrænset antal værdier, der er ikke en tilnærmelse, og enhver handling mellem en tilnærmelse og et andet tal resulterer i en tilnærmelse, afrundingsfejl er næsten uundgåelige .

Det vigtige ting er at indse, hvornår de sandsynligvis vil forårsage et problem og tage skridt til at afbøde risiciene .

Ud over David Goldberg “s essentielle Hvad enhver computerforsker t Bør vide om flydende aritmetik (genudgivet af Sun / Oracle som et tillæg til deres Numerisk Computation Guide ), som blev nævnt af thorsten , ACCU journal Overbelastning kørte en fremragende serie artikler af Richard Harris om Floating Point Blues .

Serien startede med

• Du bliver nødt til at tænke! i Overbelastning # 99 ( pdf , p5-10):

Numerisk co mputering har mange faldgruber. Richard Harris begynder at kigge efter en sølvkugle.

Den numeriske fejls drage vækkes ikke ofte fra hans søvn, men hvis den tages forsigtigt hen, vil han lejlighedsvis påføre den uforsigtige programmerings beregninger katastrofale skader.

Så meget, at nogle programmører, efter at have set ham i skovene i IEEE 754 flydende aritmetik, fraråder deres stipendiater mod at rejse i det smukke land.

I denne artikelserie skal vi udforske en verden af numerisk beregning, kontrasterende flydende aritmetik med nogle af de teknikker, der er blevet foreslået som sikrere erstatninger for det. Vi skal lære, at dragen faktisk er vidtrækkende, og at vi generelt skal træde forsigtigt, hvis vi frygter hans ødelæggende opmærksomhed.

Richard starter med at forklare taksonomien for reelle tal, rationelle, irrationelle, algebraiske og transcendentale. Han fortsætter derefter med at forklare IEEE754-repræsentation, inden han går videre til annulleringsfejl og rækkefølge for udførelsesproblemer.

Hvis du ikke læser dybere end dette, vil du have en fremragende forankring i problemerne forbundet med flydende nummer .

Hvis du dog vil vide mere, fortsætter han med

• Hvorfor fikserede point ikke helbrede dine flydende blues i Overbelastning # 100 ( pdf , p15-22)
• Hvorfor rationelle vil ikke Hær din flydende blues i Overbelastning # 101 ( pdf , s9-13)
• Hvorfor computeralgebra ikke kurerer din flydende blues i Overbelastning # 102 ( pdf , p9- 14).
• Hvorfor intervallaritmetik ikke kurerer dit flydende blues i Overbelastning 103 ( pdf , s19-24)

Han skifter derefter til at prøve at hjælpe dig med at helbrede din Calculus Blues

• Hvorfor [Indsæt algoritme her] vil ikke kurere dine calculusblues i Overbelastning 104 ( pdf , s22-24).
• Hvorfor endelige forskelle ikke helbreder din calculusblues i Overbelastning 105 ( pdf , p5-12).
• Hvorfor polynomial tilnærmelse vinder ikke din calculusblues i Overbelastning 106 ( pdf , p16-25).
• Hvorfor computeralgebra ikke kurerer din calculusblues i Overbelastning 107 ( pdf , p15-20).

og sidst men ikke mindst er der

• Hvorfor automatisk differentiering ikke kurerer din calculusblues i Overbelastning 108 ( pdf , p4-11).

Hele artikelserien er værd at se på, og i alt 66 sider er de stadig mindre end de 77 sider i Goldberg-papiret .

Mens dette serier dækker meget af det samme sted, jeg fandt det temmelig mere tilgængeligt end Goldbergs papir . Jeg fandt det også lettere at forstå de mere komplekse dele af papiret efter at have læst de tidligere Richards-artikler, og efter disse tidlige artikler forgrenede Richard sig til mange interessante områder, der ikke blev berørt af Goldberg-papiret.

Som således talte ak nævnt i kommentarer:

Som forfatter til de artikler, jeg vil gerne nævne, at jeg har oprettet interaktive versioner af dem på min blog www.thusspakeak.com startende med thusspakeak.com/ak/2013/06 .

Kommentarer

• Som forfatter af disse artikler vil jeg ‘ gerne nævne, at jeg har oprettet interaktive versioner af dem på min blog www.thusspakeak.com startende med thusspakeak.com/ak/2013/06 .
• Tak @ thusspakea.k. Jeg ‘ har tilføjet en note til mit svar, og tho se interaktive elementer fungerer meget pænt.

Nå, thorsten har det definitive link . Jeg vil tilføje:

Enhver form for repræsentation vil have en afrundingsfejl for et antal. Prøv at udtrykke 1/3 i IEEE flydende punkt eller i decimal. Ingen af dem kan gøre det nøjagtigt. Dette går ud over at besvare dit spørgsmål, men jeg har brugt denne tommelfingerregel med succes:

• Gem brugerindtastede værdier i decimal (fordi de næsten helt sikkert indtastede det i en decimalrepræsentation – meget få brugere bruger binær eller hex). På den måde har du altid den nøjagtige brugerindtastede repræsentation.
• Hvis du skal gemme brugerindtastede brøker, skal du gemme tælleren og nævneren (også i decimal)
• Hvis du har en system med flere måleenheder til den samme størrelse (som Celsius / Fahrenheit), og brugeren kan indtaste begge dele, gemme den værdi, de indtastede, og de enheder, de indtastede dem i. Forsøg ikke at konvertere og gemme som en enkelt repræsentation, medmindre du kan gøre det uden tab af præcision / nøjagtighed. Brug den lagrede værdi og enheder i alle beregninger.
• Gem maskingenererede værdier i IEEE-flydende punkt (dette kan være genererede tal ved hjælp af en elektronisk måleenhed, som en analog sensor med en A / D-konverter eller det ikke-afrundede resultat af en beregning. Bemærk, at dette ikke gælder, hvis du læser en sensor over en seriel forbindelse, og den allerede giver du værdien i et decimalformat (f.eks. 18,2 C).
• Gem bruger-synlige totaler osv. i decimal (som en bankkonto balance). Rund passende, men brug den værdi som den endelige værdi til alle fremtidige beregninger.

Kommentarer

• Jeg vil tilføje: Overvej at bruge en vilkårlig præcision matematikpakke som ARPREC eller decNumber.
• Jeg har ‘ t decimal (i modsætning til binær) har stor fordel for heltalværdier, såsom tælleren og nævneren af en brøkdel. Enten kan gemme nøjagtige heltalværdier, og binær er mere effektiv. Der ‘ er nogle omkostninger ved at konvertere frem og tilbage til input og output, men at ‘ sandsynligvis bliver oversvømmet af prisen på fysisk udfører I / O.

Hvad der tilsyneladende ikke er blevet nævnt indtil videre er begreberne med en ustabil algoritme og et dårligt betinget problem . Jeg adresserer førstnævnte først, da det synes at være en hyppigere faldgrube for uerfarne numerikere.

Overvej beregningen af beføjelserne i det (gensidige) gyldne forhold φ=0.61803…; en mulig måde at gå på det er at bruge rekursionsformlen φ^n=φ^(n-2)-φ^(n-1), startende med φ^0=1 og φ^1=φ. Hvis du kører denne rekursion i dit foretrukne computermiljø og sammenligner resultaterne med nøjagtigt evaluerede kræfter, vil du finde en langsom erosion af vigtige tal. Her er hvad der sker for eksempel i 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} 

Det påståede resultat for φ^41 har det forkerte tegn, og endnu tidligere deler de beregnede og faktiske værdier for φ^39 ingen cifre til fælles (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Algoritmen er således ustabil, og man skal ikke bruge denne rekursionsformel i unøjagtig aritmetik. Dette skyldes den iboende natur af rekursionsformlen: der er en “rådnende” og “voksende” løsning på denne rekursion, og forsøg på at beregne den “rådnende” løsning ved fremadrettet løsning, når der er en alternativ “voksende” løsning, beder om numerisk sorg. Man skal således sikre, at hans / hendes numeriske algoritmer er stabile.

Nu, videre til begrebet et dårligt betinget problem: selvom der kan være en stabil måde at gøre noget numerisk, kan det meget vel være, at det problem du har ve kan bare ikke løses af din algoritme. Dette er selve problemet skyld og ikke løsningsmetoden. Det kanoniske eksempel i numerik er løsningen på lineære ligninger, der involverer den såkaldte “Hilbert-matrix”:

The matrix er det kanoniske eksempel på en dårlig betinget matrix: forsøg på at løse et system med en stor Hilbert-matrix kan returnere en unøjagtig løsning.

Her “sa Mathematica demonstration: sammenlign resultaterne af nøjagtig aritmetik

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

og unøjagtig aritmetik

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

(Hvis du prøvede det i Mathematica , vil du bemærke et par fejlmeddelelser, der advarer om, at den dårlige tilstand vises.)

I begge tilfælde skal du blot øge præcision er ingen kur; det vil kun forsinke den uundgåelige erosion af tal.

Dette er hvad du måske står over for. Løsningerne kan være vanskelige: for det første går du enten tilbage til tegnebrættet eller vender gennem tidsskrifter / bøger / hvad som helst for at finde, hvis en anden har fundet en bedre løsning end du har; for det andet giver du enten op eller omformulerer dit problem til noget mere brugbart.

Jeg vil efterlade dig et citat fra Dianne O “Leary:

Livet kan kaste os nogle dårlige betingelser, men der er ingen god grund til at nøjes med en ustabil algoritme.

fordi basis 10 decimaltal ikke kan udtrykkes i base 2

eller med andre ord 1/10 ikke kan være omdannet til en brøkdel med en styrke på 2 i nævneren (hvilket er det flydende punktum i det væsentlige er)

Kommentarer

• Ikke ligefrem sandt: 0,5 og 0,25 kan udtrykkes i base 2. Jeg tror, du mener ” ikke alle base 10 decimaltal “.
• Mere præcist. Ikke alle brøktal kan repræsenteres nøjagtigt ved hjælp af en flydende punktotation (dvs. med. Både base 2 og base 10 har netop dette problem). Prøv at udføre 9*3.3333333 i decimal og komprimere det til 9*3 1/3
• Dette er den mest almindelige kilde til flydende punkt forvirring. .1 + .1 != .2 fordi der anvendes flydende binær kodning, ikke decimal.
• @SeanMcMillan: Og 1.0/3.0*3.0 != 1.0, fordi flydende -point binær kodning bruges, ikke trinary.

I matematik er der uendeligt mange rationelle tal . En 32 bit variabel kan kun have 2 ³² forskellige værdier, og en 64 bit variabel kun 2 ⁶⁴ værdier. Derfor er der uendeligt mange rationelle tal, der ikke har nogen præcis repræsentation.

Vi kunne komme med skemaer, der giver os mulighed for at repræsentere 1/3 perfekt eller 1/100. Det viser sig, at det til mange praktiske formål ikke er meget nyttigt. Der er en stor undtagelse: i økonomi dukker decimale brøker ofte op. Det skyldes for det meste, at økonomi i det væsentlige er en menneskelig aktivitet, ikke en fysisk aktivitet.

Derfor vælger vi normalt at bruge binært flydende punkt og afrunde enhver værdi, der ikke kan repræsenteres i binær. Men i økonomi vælger vi undertiden flydende decimaler og runde værdier til nærmeste decimalværdi .

Kommentarer

• Endnu værre, mens en uendelig (utalligt uendelig) mængde hukommelse gør det muligt for en at repræsentere alle rationelle, ville det ikke nok til at repræsentere de virkelige. Endnu værre er, at næsten alle de reelle tal ikke kan beregnes. Det bedste, vi kan gøre med en begrænset mængde hukommelse, er at tilnærme en begrænset delmængde af realerne.
• @Kevin: Du ‘ taler om de beregnelige tal, som er en lille delmængde (en delmængde med mål nul) af realerne.
• +1 for mest grundlæggende forklaring: Du ‘ forsøger at repræsentere en uendelig mængde tal med et endeligt antal bits.
• @ DavidHammen: Beregnbare tal er en lille delmængde ( af mål nul) af realerne – men hvert tal, du ‘ nogensinde arbejder med i et program, kan pr. definition beregnes.
• @Giorgio: Hvis du vælger den rigtige repræsentation, kvadratroden af 2 er repræsentativ, for eksempel som strengen "√2". (Min gamle HP-48-lommeregner var i stand til at gøre præcis det, og kvadrering af denne værdi resulterede i nøjagtigt 2.0.) Der er kun en tællelig uendelighed af repræsentative reelle tal for ethvert endelig repræsentation – men ingen beregning kan give et tal, der i princippet ikke er repræsentativt. I praksis begrænser binært flydepunkt drastisk antallet af repræsentable tal med fordelen af flammende hastighed og lille lagring i forhold til symbolske repræsentationer.

det eneste rigtig oplagte “afrundingsproblem” med flydende tal, jeg tænker på, er med glidende gennemsnitsfiltre:

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

for at få dette til at fungere uden opbygningen af støj, vil du sikre dig, at $ x [n] $, du tilføjer i de aktuelle prøver, er nøjagtig den samme som $ x [nN] $, du trækker $ N $ -prøver i fremtiden. Hvis det ikke er tilfældet, så er det, der er anderledes, en lille turd, der sidder fast i din forsinkelseslinje og aldrig kommer ud. det er fordi dette glidende gennemsnitsfilter faktisk er bygget med en IIR, der har en marginalt stabil pol på $ z = 1 $ og et nul, der annullerer det indeni. men det er en integrator, og alt lort, der bliver integreret og ikke helt fjernet, vil eksistere i integratorsummen for evigt. det er her fast punkt ikke har det samme problem, som flydende tal gør.

Kommentarer

• hej, fungerer ikke ‘ t $ LaTeX $ matematisk markering i prog.SE forum ??? at ‘ er virkelig halt, hvis det ikke ‘ t.
• Se dette på meta.SO og sammenkædede spørgsmål