Vad orsakar avrundningsfel med flytande punkter?

Detta beror på att vissa fraktioner behöver en mycket stor (eller till och med oändlig) plats för att uttryckas utan avrundning. Detta gäller för decimalnotation lika mycket som för binär eller någon annan. Om du skulle begränsa mängden decimaler som ska användas för dina beräkningar (och undvika att göra beräkningar i bråknotation) måste du avrunda till och med ett enkelt uttryck som 1/3 + 1/3. I stället för att skriva 2/3 som ett resultat måste du skriva 0,333333 + 0,33333 = 0,666666 vilket inte är identiskt med 2/3.

Om det är en dator är antalet siffror begränsat av den tekniska karaktären. av dess minne och CPU-register. Den binära notationen som används internt lägger till några fler svårigheter. Datorer kan normalt inte uttrycka siffror i bråknotation, även om vissa programmeringsspråk lägger till denna förmåga, vilket gör att dessa problem kan undvikas till en viss grad.

Vad varje datavetenskapare borde veta om flytpunkt-aritmetik

Kommentarer

• Spot on. Men jag skulle också notera att vissa siffror som avsluta i decimal don ’ t avsluta i binärt. Speciellt 0,1 är ett återkommande tal i binärt och så inget flytande punkt binärt tal kan exakt representera 0,1.
• Flytande poäng är inte ’ t bara användbart för många decimaler. 32-bitars heltal kan bara räkna upp till cirka 4 miljarder, men en 32-bitars float kan vara nästan oändligt stor.
• I synnerhet är de fraktioner som vi kan uttrycka som ändliga decimaler de vars nämnare ’ primfaktorisering bara innehåller 2 och 5 (t.ex. kan vi uttrycka 3/10 och 7/25 , men inte 11/18). När vi går till binär tappar vi faktorn 5 så att endast de dyadiska rationella (t.ex. 1/4, 3/128) kan uttryckas exakt.

Avrundningsfel kommer främst från det faktum att oändligheten av alla reella tal kan omöjligt representeras av slutligt minne på en dator , än mindre en liten bit minne, till exempel en enda flytpunktvariabel , så många lagrade nummer är bara approximationer av antalet de är avsedda att representera.

Eftersom det bara finns ett begränsat antal värden som är inte en approximation, och varje operation mellan en approximation och ett annat nummer resulterar i en approximation, avrundningsfel är nästan oundvikliga .

Det viktiga saken är att inse när de sannolikt orsakar ett problem och vidta åtgärder för att mildra riskerna .

Förutom David Goldberg : s väsentliga Vad varje datavetare t Bör veta om flytpunkt-aritmetik (ompubliceras av Sun / Oracle som en bilaga till deras Numeriska Beräkningsguide ), som nämndes av thorsten , ACCU journal Överbelastning körde en utmärkt serie artiklar av Richard Harris om Floating Point Blues .

Serien började med

• Du måste tänka! i Överbelastning # 99 ( pdf , p5-10):

Numerisk co mputing har många fallgropar. Richard Harris börjar leta efter en silverkula.

Siffrans drake väcks inte ofta från sin sömn, men om han försiktigt närmar sig kommer han ibland att orsaka katastrofala skador på den otillbörliga programmerarens beräkningar.

Så mycket att vissa programmerare, efter att ha kollat på honom i skogarna i IEEE 754 flytande aritmetik, rekommenderar sina kamrater att resa i det rättvisa landet.

I den här serien av artiklar ska vi utforska världen av numerisk beräkning, kontrasterande flytpunktsberäkning med några av de tekniker som har föreslagits som säkrare ersättare för den. Vi ska lära oss att drakens territorium faktiskt är långtgående och att vi i allmänhet måste trampa försiktigt om vi fruktar hans förödande uppmärksamhet.

Richard börjar med att förklara taxonomin för reella tal, rationella, irrationella, algebraiska och transcendentala. Han fortsätter sedan med att förklara IEEE754-representation, innan han går vidare till avbokningsfel och ordning på exekveringsproblem.

Om du inte läser något djupare än detta kommer du att ha en utmärkt grund i problemen associerade med flytande punktnummer .

Om du vill veta mer fortsätter han dock med

• Varför Fixed Point vann inte bota dina flytande blues i Överbelastning # 100 ( pdf , p15-22)
• Varför Rationals inte Bota dina flytande blues i Överbelastning # 101 ( pdf , p9-13)
• Varför datoralgebra inte botar dina flytande blues i Överbelastning # 102 ( pdf , p9- 14).
• Varför intervallaritmetik inte botar din flytande blues i Överbelastning 103 ( pdf , s19-24)

Han byter sedan till att försöka hjälpa dig att bota din Calculus Blues

• Varför [Infoga algoritm här] kommer inte att bota dina kalkylblues i Överbelastning 104 ( pdf , s22-24).
• Varför ändliga skillnader inte botar dina kalkylblues i Överbelastning 105 ( pdf , p5-12).
• Varför Polynomial approximation vinner inte att bota din Calculus Blues i Överbelastning 106 ( pdf , p16-25).
• Varför datoralgebra inte botar din Calculus Blues i Överbelastning 107 ( pdf , p15-20).

och sist men inte minst finns

• Varför automatisk differentiering inte botar din Calculus Blues i Överbelastning 108 ( pdf , p4-11).

Hela artikelserien är väl värt att titta på, och totalt 66 sidor är de fortfarande mindre än de 77 sidorna i Goldbergpapper .

Även om detta serier täcker mycket av samma mark, jag tyckte att det var mer tillgängligt än Goldbergs papper . Jag tyckte också att det var lättare att förstå de mer komplexa delarna av tidningen efter att ha läst de tidigare artiklarna från Richards och efter de tidiga artiklarna förgrenar Richard sig till många intressanta områden som inte berörs av Goldberg-tidningen.

Som så talade ak som nämns i kommentarer:

Som författare till de artiklarna jag vill nämna att jag har skapat interaktiva versioner av dem på min blogg www.thusspakeak.com med thusspakeak.com/ak/2013/06 .

Kommentarer

• Som författare till dessa artiklar vill jag ’ nämna att jag har skapat interaktiva versioner av dem på min blogg www.thusspakeak.com som börjar med thusspakeak.com/ak/2013/06 .
• Tack @ thusspakea.k. Jag ’ har lagt till en anteckning till mitt svar, och tho interaktiva element fungerar mycket snyggt.

Tja, thorsten har den slutgiltiga länken . Jag skulle tillägga:

Varje form av representation kommer att ha något avrundningsfel för något nummer. Försök att uttrycka 1/3 i IEEE-flytpunkt eller i decimal. Ingen av dem kan göra det exakt. Detta går utöver att svara på din fråga, men jag har använt den här tumregeln framgångsrikt:

• Lagra användarinmatade värden i decimal (eftersom de nästan säkert angav den i en decimalrepresentation – väldigt få användare kommer att använda binär eller hex). På det sättet har du alltid den exakta användarinmatade representationen.
• Om du måste lagra användarinmatade fraktioner, lagra täljaren och nämnaren (även i decimal)
• Om du har en system med flera måttenheter för samma kvantitet (som Celsius / Fahrenheit), och användaren kan ange båda, spara värdet de angav och de enheter de angav dem i. Försök inte konvertera och spara som en enda representation, såvida du inte kan göra det utan förlust av precision / noggrannhet. Använd de lagrade värdena och enheterna i alla beräkningar.
• Lagra maskingenererade värden i IEEE-flytpunkt (detta kan genereras siffror av en elektronisk mätanordning, som en analog sensor med en A / D-omvandlare, eller det oavgränsade resultatet av en beräkning. Observera att detta inte gäller om du läser en sensor över en seriell anslutning och den redan ger du värdet i ett decimalformat (t.ex. 18,2 C).
• Lagra användarsynliga summor etc. i decimaler (som ett bankkonto balans). Runda på lämpligt sätt, men använd det värdet som det slutgiltiga värdet för alla framtida beräkningar.

Kommentarer

• Jag vill lägga till: Överväg att använda en godtycklig precision matematikpaket som ARPREC eller decNumber.
• Jag har ’ t decimal (i motsats till binär) har mycket nytta för helvärden, t.ex. täljaren och nämnare för en bråkdel. Antingen kan lagra exakta heltalsvärden och binär är effektivare. Det finns ’ en del kostnader för att konvertera fram och tillbaka för in- och utdata, men det är troligt att ’ kommer att överbelastas av fysisk utför I / O.

Det som verkar inte ha nämnts hittills är begreppen en instabil algoritm och ett dåligt problem . Jag kommer att ta itu med den förstnämnda, eftersom det verkar vara en vanligare fallgrop för nybörjare numeriker.

Tänk på beräkningen av krafterna för det (ömsesidiga) gyllene förhållandet φ=0.61803…; en möjlig väg att gå igenom är att använda rekursionsformeln φ^n=φ^(n-2)-φ^(n-1), börja med φ^0=1 och φ^1=φ. Om du kör denna rekursion i din favoritdatormiljö och jämför resultaten med noggrant utvärderade krafter, kommer du att hitta en långsam erosion av betydande siffror. Här är vad som händer till exempel 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ådda resultatet för φ^41 har fel tecken, och ännu tidigare delar de beräknade och faktiska värdena för φ^39 inga siffror gemensamt (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Algoritmen är alltså instabil, och man bör inte använda denna rekursionsformel i felaktig aritmetik. Detta beror på rekursionsformelens inneboende natur: det finns en ”förfallande” och ”växande” lösning på denna rekursion, och att försöka beräkna den ”förfallna” lösningen genom framåtlösning när det finns en alternativ ”växande” lösning ber om numerisk sorg. Man bör alltså se till att hans / hennes numeriska algoritmer är stabila.

Nu, vidare till konceptet med ett dåligt konditionerat problem: även om det kan finnas ett stabilt sätt att göra något numeriskt, kan det mycket väl vara det problemet du har vi kan bara inte lösas av din algoritm. Det här är själva problemet och inte lösningsmetoden. Det kanoniska exemplet i numerik är lösningen av linjära ekvationer som involverar den så kallade ”Hilbert-matrisen”:

matris är det kanoniska exemplet på en dålig matris: att försöka lösa ett system med en stor Hilbert-matris kan returnera en felaktig lösning.

Här ”sa Mathematica demonstration: jämför resultaten av exakt 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}} 

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

(Om du försökte det i Mathematica , kommer du att notera några felmeddelanden som varnar för dålig konditionering.)

I båda fallen ökar du helt enkelt precision är inget botemedel; det kommer bara att försena den oundvikliga erosionen av siffror.

Detta är vad du kan möta. Lösningarna kan vara svåra: för det första går du antingen tillbaka till ritbordet eller vassar genom tidskrifter / böcker / vad som helst för att hitta om någon annan har kommit med en bättre lösning än du har; för det andra ger du antingen upp eller omformulerar ditt problem till något mer smidigt.

Jag lämnar ett citat från Dianne O ”Leary:

Livet kan kasta oss några dåliga problem, men det finns ingen god anledning att nöja sig med en instabil algoritm.

eftersom bas 10 decimaltal inte kan uttryckas i bas 2

eller med andra ord 1/10 inte kan vara förvandlas till en bråkdel med kraften 2 i nämnaren (vilket är vad flytande punktnummer i huvudsak är)

Kommentarer

• Inte exakt sant: 0,5 och 0,25 kan uttryckas i bas 2. Jag tror att du menar ” inte alla bas 10 decimaler ”.
• Mer exakt. Inte alla bråknummer kan representeras exakt med hjälp av en flytpunktsnotation (dvs med. Både bas 2 och bas 10 har exakt detta problem). Försök att göra 9*3.3333333 i decimal och komprimera det till 9*3 1/3
• Detta är den vanligaste källan till flytpunkt förvirring. .1 + .1 != .2 eftersom binär kodning av flytande punkt används, inte decimal.
• @SeanMcMillan: Och 1.0/3.0*3.0 != 1.0, eftersom flytande -punkts binär kodning används, inte trinarisk.

I matematik finns det oändligt många rationella tal . En 32-bitars variabel kan bara ha två ³² olika värden och en 64-bitars variabel endast 2 ⁶⁴ -värden. Därför finns det oändligt många rationella tal som inte har någon exakt representation.

Vi kan komma med scheman som gör att vi kan representera 1/3 perfekt, eller 1/100. Det visar sig att det för många praktiska ändamål inte är mycket användbart. Det finns ett stort undantag: inom ekonomi dyker decimalfraktioner ofta upp. Det beror främst på att ekonomi i huvudsak är en mänsklig aktivitet, inte en fysisk aktivitet.

Därför väljer vi vanligtvis att använda binär flytpunkt och avrunda valfritt värde som inte kan representeras i binärt. Men i ekonomi väljer vi ibland decimal flytpunkt och runda värden till närmaste decimalvärde .

Kommentarer

• Ännu värre, medan en oändlig (oändligt oändlig) mängd minne skulle göra det möjligt för en att representera alla rationella, skulle det inte tillräckligt för att representera realerna. Ännu värre är att nästan alla reella tal inte är beräkningsbara tal. Det bästa vi kan göra med en begränsad mängd minne är att ungefärliga en undergrupp med begränsat intervall av realerna.
• @Kevin: Du ’ talar om de beräknbara siffrorna, vilket är en liten delmängd (en delmängd med mått noll) av realerna.
• +1 för mest grundläggande förklaring: Du ’ försöker representera en oändlig mängd siffror med ett ändligt antal bitar.
• @ DavidHammen: Beräknbara tal är en liten delmängd ( av måttet noll) av realerna – men varje nummer som du ’ någonsin kommer att arbeta med i ett program är per definition beräknbart.
• @Giorgio: Om du väljer rätt representation, kvadratroten av 2 är representerbar, till exempel som strängen "√2". (Min gamla HP-48-miniräknare kunde göra exakt det och att kvadrera det värdet resulterade i exakt 2.0.) Det finns bara en räknbar oändlighet av representerbara reella tal för alla slutlig representation – men ingen beräkning kan ge ett tal som i princip inte är representativt. I praktiken begränsar binär flytpunkt drastiskt uppsättningen representerbara tal, med fördelen med flammande hastighet och liten lagring i förhållande till symboliska representationer.

det enda riktigt uppenbara ”avrundningsfrågan” med flytande siffror som jag tänker på är med glidande medelfilter:

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

för att detta ska fungera utan om du bygger buller vill du se till att $ x [n] $ du lägger till i de aktuella exemplen är exakt densamma som $ x [nN] $ du kommer att subtrahera $ N $ -prover i framtiden. om det inte är det som är annorlunda är en liten turd som fastnar i din fördröjningslinje och aldrig kommer ut. det beror på att detta rörliga medelfilter faktiskt är byggt med en IIR som har en marginellt stabil pol vid $ z = 1 $ och en noll som avbryter det inuti. men det är en integrator och allt skit som integreras och inte helt tas bort kommer att finnas i integratorsumman för alltid. det är här fixpunkt inte har samma problem som flytande punktnummer gör.

Kommentarer

• hej, fungerar inte ’ t $ LaTeX $ matematisk markering i prog.SE-forumet ??? att ’ är riktigt halt om det inte ’ t.
• Se detta på meta.SO och länkade frågor