Hva forårsaker feil med avrunding av flytende punkt?

Dette er fordi noen brøker trenger en veldig stor (eller til og med uendelig) mengde steder som skal uttrykkes uten avrunding. Dette gjelder for desimalnotasjon like mye som for binær eller annen. Hvis du begrenser antall desimaler som skal brukes til beregningene dine (og unngår å gjøre beregninger i brøknotasjon), må du avrunde til og med et enkelt uttrykk som 1/3 + 1/3. I stedet for å skrive 2/3 som et resultat, må du skrive 0.33333 + 0.33333 = 0.66666 som ikke er identisk med 2/3.

I tilfelle en datamaskin er antall sifre begrenset av den tekniske naturen. av minne- og CPU-registrene. Den binære notasjonen som brukes internt, gir noen flere vanskeligheter. Datamaskiner kan normalt ikke uttrykke tall i brøknotasjon, selv om noen programmeringsspråk legger til denne muligheten, noe som gjør at disse problemene til en viss grad kan unngås.

Hva enhver datamaskinforsker burde vite om flytepunktsaritmetikk

Kommentarer

• Spot on. Men jeg vil også merke at noen tall som avsluttes i desimal don ‘ t avsluttes i binær. Spesielt er 0,1 et gjentakende tall i binært og så ingen flytende punkt binært tall kan nøyaktig representere 0,1.
• Flytende poeng er ikke ‘ t bare nyttig for mange desimaler. 32-biters heltall kan bare telle opptil omtrent 4 milliarder, men en 32-biters flottør kan være nesten uendelig stor.
• Spesielt er brøkene vi kan uttrykke som endelige desimaler de hvis nevnere ‘ primfaktorisering inneholder bare 2 og 5 (f.eks. kan vi uttrykke 3/10 og 7/25 , men ikke 11/18). Når vi går over til binær, mister vi faktoren 5, slik at bare de dyadiske rasjonellene (f.eks. 1/4, 3/128) kan uttrykkes nøyaktig.

Primært kommer avrundingsfeil fra det faktum at uendigheten av alle reelle tall kan umulig representeres av endelig minne på en datamaskin , enn si et lite stykke minne, for eksempel en enkelt variabel med flytende punkt , så mange lagrede tall er bare tilnærminger av antallet de er ment å representere.

Siden det bare er et begrenset antall verdier som er ikke en tilnærming, og enhver operasjon mellom en tilnærming og et annet tall resulterer i en tilnærming, avrundingsfeil er nesten uunngåelige .

Det viktige tingen er å innse når de sannsynligvis vil forårsake et problem og ta skritt for å redusere risikoen .

I tillegg til David Goldberg «s essensielle Hva hver datamaskinforsker t Bør vite om flytepunktsaritmetikk (re-publisert av Sun / Oracle som et vedlegg til Numerisk Beregningsveiledning ), som ble nevnt av thorsten , ACCU journal Overbelastning kjørte en utmerket serie artikler av Richard Harris om Floating Point Blues .

Serien startet med

• Du må tenke! i Overbelastning # 99 ( pdf , p5-10):

Numerisk co mputering har mange fallgruver. Richard Harris begynner å lete etter en sølvkule.

Dragen med numeriske feil blir ikke ofte vekket av søvnen, men hvis den blir forsiktig nærmet, vil han av og til påføre den uforsiktige programmererens beregninger katastrofale skader.

Så mye at noen programmerere, etter å ha sjanset på ham i skogene til IEEE 754 flytepunktsregning, råder sine stipendiater mot å reise i det rettferdige landet.

I denne artikkelserien skal vi utforske verden av numerisk databehandling, kontrasterende flytepunktsaritmetikk med noen av teknikkene som er blitt foreslått som tryggere erstatninger for den. Vi skal lære at dragenes territorium virkelig er vidtrekkende og at vi generelt må trå forsiktig hvis vi frykter hans ødeleggende oppmerksomhet.

Richard begynner med å forklare taksonomien til reelle tall, rasjonelle, irrasjonelle, algebraiske og transcendentale. Han fortsetter deretter med å forklare IEEE754-fremstilling, før han går videre til avbestillingsfeil og rekkefølge for utførelsesproblemer.

Hvis du ikke leser dypere enn dette, vil du ha en utmerket forankring i problemene knyttet til flytende punktum .

Hvis du imidlertid vil vite mer, fortsetter han med

• Hvorfor vant Fixed Point ikke å kurere dine flytende blues i Overbelastning # 100 ( pdf , p15-22)
• Hvorfor rasjonelle vil ikke Cure Your Floating Point Blues i Overbelastning # 101 ( pdf , p9-13)
• Hvorfor datamaskinalgebra ikke vil kurere dine flytende blues i Overbelastning # 102 ( pdf , p9- 14).
• Hvorfor intervallaritmetikk ikke vil kurere dine flytende blues i Overbelastning 103 ( pdf , p19-24)

Han bytter deretter til å prøve å hjelpe deg med å kurere Calculus Blues

• Hvorfor [Sett inn algoritme her] vil ikke kurere calculusblues i Overbelastning 104 ( pdf , s22-24).
• Hvorfor endelige forskjeller ikke vil kurere calculusblues i Overbelastning 105 ( pdf , p5-12).
• Hvorfor tilnærming til polynom vil ikke kurere kalkulatorblues i Overbelastning 106 ( pdf , p16-25).
• Hvorfor datamaskinalgebra ikke vil kurere kalkulasjonsblues i Overbelastning 107 ( pdf , p15-20).

og sist men ikke minst, det er

• Hvorfor automatisk differensiering ikke vil kurere calculusblues i Overbelastning 108 ( pdf , p4-11).

Hele artikelserien er vel verdt å se på, og til sammen 66 sider er de fortsatt mindre enn de 77 sidene i Goldberg-papiret .

Mens dette serier dekker mye av det samme bakken, jeg fant det ganske mer tilgjengelig enn Goldbergs papir . Jeg fant det også lettere å forstå de mer komplekse delene av papiret etter å ha lest de tidligere Richards-artiklene, og etter de tidlige artiklene forgrener Richard seg til mange interessante områder som ikke berøres av Goldberg-papiret.

Som således snakket ak nevnt i kommentarene:

Som forfatter av de artiklene jeg vil nevne at jeg har laget interaktive versjoner av dem på bloggen min www.thusspakeak.com som starter med thusspakeak.com/ak/2013/06 .

Kommentarer

• Som forfatter av disse artiklene vil jeg ‘ nevne at jeg har laget interaktive versjoner av dem på bloggen min www.thusspakeak.com som starter med thusspakeak.com/ak/2013/06 .
• Takk @ thusspakea.k. Jeg ‘ har lagt til et notat til mitt svar, og tho se interaktive elementer fungerer veldig bra.

Vel, thorsten har den definitive lenken . Jeg vil legge til:

Enhver form for representasjon vil ha noen avrundingsfeil for noen tall. Prøv å uttrykke 1/3 i IEEE flytende punkt, eller i desimal. Ingen av dem kan gjøre det nøyaktig. Dette går utover å svare på spørsmålet ditt, men jeg har brukt denne tommelfingerregelen med hell:

• Lagre brukerinntastede verdier i desimal (fordi de nesten helt sikkert skrev inn den i en desimalrepresentasjon – svært få brukere vil bruke binær eller hex). På den måten har du alltid den nøyaktige brukerinntastede representasjonen.
• Hvis du må lagre brukerinntatte brøker, lagrer teller og nevner (også i desimal)
• Hvis du har en system med flere måleenheter for samme mengde (som Celsius / Fahrenheit), og brukeren kan angi begge, lagre verdien de skrev inn og enhetene de skrev inn dem i. Ikke prøv å konvertere og lagre som en enkelt representasjon, med mindre du kan gjøre det uten tap av presisjon / nøyaktighet. Bruk de lagrede verdien og enhetene i alle beregninger.
• Lagre maskingenererte verdier i IEEE-flytpunkt (dette kan være genererte tall av en elektronisk måleenhet, som en analog sensor med en A / D-omformer, eller resultatet av en beregning som ikke er avrundet. Merk at dette ikke gjelder hvis du leser en sensor over en seriell tilkobling og den allerede gir du verdien i desimalformat (f.eks. 18,2 C).
• Lagre totalverdier som kan vises av brukeren, etc., i desimal (som en bankkonto balansere). Rund passende, men bruk den verdien som den endelige verdien for alle fremtidige beregninger.

Kommentarer

• Jeg vil legge til: Vurder å bruke en vilkårlig presisjonsmatematikkpakke som ARPREC eller decNumber.
• Jeg har ikke ‘ t desimal (i motsetning til binær) har stor fordel for heltallverdier, for eksempel teller og nevner av en brøkdel. Enten kan lagre nøyaktige heltallverdier, og binær er mer effektiv. Det er ‘ noen kostnader ved å konvertere frem og tilbake for input og output, men det er sannsynlig at ‘ vil bli oversvømt av fysisk utføre I / O.

Det som tilsynelatende ikke har blitt nevnt så langt er begrepene i en ustabil algoritme og et dårlig betinget problem . Jeg tar opp førstnevnte først, da det ser ut til å være en hyppigere fallgruve for uerfarne numerikere.

Vurder beregningen av kreftene til det (gjensidige) gyldne forholdet φ=0.61803…; en mulig måte å gå frem på er å bruke rekursjonsformelen φ^n=φ^(n-2)-φ^(n-1), og starte med φ^0=1 og φ^1=φ. Hvis du kjører denne rekursjonen i ditt favorittdatamiljø og sammenligner resultatene med nøyaktig evaluerte krefter, vil du finne en langsom erosjon av viktige tall. Her er hva som skjer 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åtte resultatet for φ^41 har feil tegn, og enda tidligere deler de beregnede og faktiske verdiene for φ^39 ingen sifre til felles (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Algoritmen er altså ustabil, og man skal ikke bruke denne rekursjonsformelen i unøyaktig regning. Dette skyldes den iboende naturen til rekursjonsformelen: det er en «forfallende» og «voksende» løsning på denne rekursjonen, og prøver å beregne den «forfallende» løsningen ved fremoverløsning når det er en alternativ «voksende» løsning, ber om numerisk sorg. Man bør således sørge for at hans / hennes numeriske algoritmer er stabile.

Nå, videre til konseptet med et dårlig betinget problem: selv om det kan være en stabil måte å gjøre noe numerisk, kan det veldig bra være at problemet du har Vi kan bare ikke løses av algoritmen din. Dette er feilen i selve problemet, og ikke løsningsmetoden. Det kanoniske eksemplet i numerikk er løsningen på lineære ligninger som involverer den såkalte «Hilbert-matrisen»:

The matrise er det kanoniske eksemplet på en dårlig betinget matrise: å prøve å løse et system med en stor Hilbert-matrise kan returnere en unøyaktig løsning.

Her «sa Mathematica demonstrasjon: sammenlign resultatene av eksakt aritmetikk

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øyaktig aritmetikk

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øvde det i Mathematica , vil du merke deg noen feilmeldinger som advarer om dårlig tilstand som vises.)

I begge tilfeller øker du bare presisjon er ingen kur; det vil bare forsinke den uunngåelige erosjonen av figurer.

Dette er hva du kan møte. Løsningene kan være vanskelige: for det første går du enten tilbake til tegnebrettet, eller vater gjennom tidsskrifter / bøker / hva som helst for å finne ut om noen andre har kommet med en bedre løsning enn deg; for det andre gir du deg enten opp, eller omformulerer problemet ditt til noe mer gjennomførbart.

Jeg vil gi deg et sitat fra Dianne O «Leary:

Livet kan kaste oss noen dårlig betingede problemer, men det er ingen god grunn til å nøye oss med en ustabil algoritme.

fordi basis 10 desimaltall ikke kan uttrykkes i base 2

eller med andre ord 1/10 ikke kan være transformert til en brøkdel med kraften 2 i nevneren (som er det flytende tall egentlig er)

Kommentarer

• Ikke akkurat sant: 0,5 og 0,25 kan uttrykkes i base 2. Jeg tror du mener » ikke alle basale 10 desimaltall «.
• Mer nøyaktig. Ikke alle brøkstall kan vises nøyaktig ved hjelp av en flytende punktnotasjon (dvs. med. Både base 2 og base 10 har akkurat dette problemet). Prøv å gjøre 9*3.3333333 i desimal og kompreter det til 9*3 1/3
• Dette er den vanligste kilden til flytende punkt forvirring. .1 + .1 != .2 fordi det brukes binær koding med flytende punkt, ikke desimal.
• @SeanMcMillan: Og 1.0/3.0*3.0 != 1.0, fordi flytende -punkt binær koding brukes, ikke trinary.

I matematikk er det uendelig mange rasjonelle tall . En 32 bit variabel kan bare ha 2 ³² forskjellige verdier, og en 64 bit variabel bare 2 ⁶⁴ verdier. Derfor er det uendelig mange rasjonelle tall som ikke har noen presis representasjon.

Vi kunne komme med ordninger som tillater oss å representere 1/3 perfekt, eller 1/100. Det viser seg at dette for mange praktiske formål ikke er veldig nyttig. Det er et stort unntak: i økonomi dukker ofte desimalfraksjoner opp. Det er hovedsakelig fordi økonomi egentlig er en menneskelig aktivitet, ikke en fysisk aktivitet.

Derfor velger vi vanligvis å bruke binært flytende punkt, og runde en hvilken som helst verdi som ikke kan vises i binær. Men i økonomi velger vi noen ganger desimal flytende punkt, og runde verdier til nærmeste desimalverdi .

Kommentarer

• Enda verre, mens en uendelig (uendelig uendelig) mengde minne vil gjøre det mulig for en å representere alle rasjonellene, ville det ikke nok til å representere realene. Enda verre, nesten alle reelle tall er ikke beregningsbare tall. Det beste vi kan gjøre med en endelig mengde minne er å tilnærme en endelig rekke undergrupper av realene.
• @Kevin: Du ‘ snakker om de beregnbare tallene, som er en liten delmengde (en delmengde med mål null) av realene.
• +1 for mest grunnleggende forklaring: Du ‘ prøver å representere en uendelig mengde tall med et endelig antall biter.
• @ DavidHammen: Beregnbare tall er en liten delmengde ( av mål null) av realene – men hvert tall du ‘ vil jobbe med i et program, kan per definisjon beregnes.
• @Giorgio: Hvis du velger riktig representasjon, kvadratroten til 2 er representabel, for eksempel som strengen "√2". (Den gamle HP-48-kalkulatoren min var i stand til å gjøre akkurat det, og kvadrering av denne verdien resulterte i nøyaktig 2.0.) Det er bare en tellbar uendelighet av representerbare reelle tall for alle endelig representasjon – men ingen beregninger kan gi et tall som i prinsippet ikke er representativt. I praksis begrenser binært flytpunkt drastisk settet med representerbare tall, med fordelen av flammende hastighet og liten lagring i forhold til symbolske representasjoner.

det eneste veldig åpenbare «avrundingsproblemet» med flytende tall jeg tenker på er med glidende gjennomsnittlige filtre:

$$ \ 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 å få dette til å fungere uten på grunn av støy, vil du forsikre deg om at $ x [n] $ du legger til i de aktuelle prøvene er nøyaktig den samme som $ x [nN] $ du vil trekke $ N $ -prøver inn i fremtiden. Hvis det ikke er det, er det som er annerledes en liten turd som setter seg fast i forsinkelseslinjen din og aldri kommer ut. det er fordi dette glidende gjennomsnittsfilteret faktisk er bygget med en IIR som har en marginalt stabil pol på $ z = 1 $ og et null som avbryter det inni. men det er en integrator, og alt dritt som blir integrert og ikke helt fjernet, vil eksistere i integratorsummen for alltid. det er her fastpunkt ikke har det samme problemet som flytende tall gjør.

Kommentarer

• hei, fungerer ikke ‘ t $ LaTeX $ matematikkoppmerking i prog.SE-forumet ??? at ‘ er veldig halt hvis det ikke ‘ t.
• Se dette på meta.SO og koblede spørsmål