Ce cauzează erori de rotunjire în virgulă mobilă?

Acest lucru se datorează faptului că unele fracții au nevoie de o cantitate foarte mare (sau chiar infinită) de locuri pentru a fi exprimate fără rotunjire. Acest lucru este valabil atât pentru notația zecimală, cât și pentru cea binară sau oricare alta. Dacă ați limita cantitatea de zecimale de utilizat pentru calculele dvs. (și ați evita efectuarea calculelor în notație de fracție), ar trebui să rotunjiți chiar și o expresie simplă ca 1/3 + 1/3. În loc să scrieți 2/3 ca rezultat, va trebui să scrieți 0,33333 + 0,33333 = 0,66666, care nu este identic cu 2/3.

În cazul unui computer, numărul de cifre este limitat de natura tehnică a memoriei sale și a registrelor CPU. Notația binară utilizată intern adaugă câteva dificultăți. În mod normal, computerele nu pot exprima numerele în notație de fracție, deși unele limbaje de programare adaugă această capacitate, ceea ce permite evitarea acestor probleme într-un anumit grad.

Ce ar trebui să știe fiecare informatician despre aritmetica în virgulă plutitoare

Comentarii

• La fața locului. Dar aș mai observa că unele numere care terminați în zecimal don ‘ t terminați în binar. În special 0,1 este un număr recurent în binar și deci niciun număr binar în virgulă mobilă nu poate reprezenta exact 0,1.
• Flotant punctele nu sunt ‘ doar utile pentru o mulțime de zecimale. Numerele întregi de 32 de biți pot conta doar până la aproximativ 4 miliarde, dar un float de 32 de biți poate fi aproape infinit de mare.
• În special, fracțiile pe care le putem exprima ca zecimale finite sunt cele ale căror numitori ‘ factorizarea primară conține doar 2 și 5 (de exemplu, putem exprima 3/10 și 7/25 , dar nu 11/18). Când trecem la binar, pierdem factorul 5, astfel încât numai raționalele diadice (de exemplu 1/4, 3/128) pot fi exprimate exact.

În primul rând, erorile de rotunjire provin din faptul că infinitatea tuturor numerelor reale nu poate fi reprezentat de memoria finită a unui computer , darămite de o mică porțiune de memorie, cum ar fi o singură variabilă în virgulă mobilă , așa că multe numere stocate sunt doar aproximări ale numărului pe care trebuie să îl reprezinte.

Deoarece există doar un număr limitat de valori care nu sunt nu o aproximare și orice operație între o aproximare și un alt număr are ca rezultat o aproximare, erorile de rotunjire sunt aproape inevitabile .

Important lucrul este să vă dați seama când este posibil să cauzeze o problemă și să luați măsuri pentru a atenua riscurile .

În plus față de David Goldberg „esențial Ce înseamnă fiecare computer Ar trebui să știți despre aritmetica în virgulă plutitoare (reeditată de Sun / Oracle ca apendice la numerică Ghid de calcul ), care a fost menționat de thorsten , ACCU jurnal Suprasarcină a rulat o serie excelentă de articole de Richard Harris despre Blues cu virgulă mobilă .

Seria a început cu

• Vei avea de gândit! în Suprasolicitare # 99 ( pdf , p5-10):

Numerical co mputingul are multe capcane. Richard Harris începe să caute un glonț de argint.

Dragonul erorii numerice nu este adesea ridicat din somnul său, dar dacă este abordat cu neatenție, el va provoca ocazional daune catastrofale calculelor programatorului incorect. >

Atât de mult încât unii programatori, după ce s-au întâmplat cu el în pădurile aritmetice în virgulă mobilă IEEE 754, își sfătuiesc semenii să nu călătorească în acel tărâm corect.

În această serie de articole vom explora lumea calculelor numerice, contrastând aritmetica cu virgulă mobilă cu unele dintre tehnicile care au fost propuse ca înlocuiri mai sigure pentru aceasta. Vom învăța că teritoriul dragonului este cu adevărat amplu și că, în general, trebuie să călcăm cu atenție dacă ne temem de atenție devastatoare.

Richard începe explicând taxonomia numerelor reale, rațională, irațională, algebrică și transcendentală. Apoi continuă să explice reprezentarea IEEE754, înainte de a trece la erori de anulare și la ordinea problemelor de execuție.

Dacă nu citiți mai adânc decât aceasta, veți avea o bază excelentă în problemele asociate cu numerele în virgulă mobilă .

Dacă totuși doriți să aflați mai multe, el continuă cu

• De ce nu a câștigat punctul fix” să-ți vindeci bluesul în virgulă plutitoare în Suprasarcină # 100 ( pdf , p15-22)
• De ce raționalele nu vor Cure-ți bluesul în virgulă plutitoare în Suprasolicitare # 101 ( pdf , p9-13)
• De ce algebra computerului nu vă va vindeca bluesul în virgulă plutitoare în Suprasarcină # 102 ( pdf , p9- 14).
• De ce aritmetica intervalelor nu vă va vindeca bluesul în virgulă mobilă în Suprasolicitare 103 ( pdf , p19-24)

Apoi trece la încercarea de a vă ajuta să vă vindecați Blues Calculus

• De ce [Inserați algoritmul aici] nu vă va vindeca calculul Blues în Suprasolicitare 104 ( pdf , p22-24).
• De ce diferențele finite nu vă vor vindeca calculul Blues în Suprasolicitare 105 ( pdf , p5-12).
• De ce a câștigat aproximarea polinomială „pentru a-ți vindeca calculul Blues în Suprasolicitare 106 ( pdf , p16-25).
• De ce algebra computerului nu vă va vindeca calculul Blues în Suprasarcină 107 ( pdf , p15-20).

și nu în ultimul rând, există

• De ce diferențierea automată nu vă va vindeca calculul Blues în Suprasolicitare 108 ( pdf , p4-11).

Întreaga serie de articole este merită să ne uităm și, în total, la 66 de pagini, acestea sunt încă mai mici decât cele 77 de pagini ale lucrării Goldberg .

În timp ce aceasta seria acoperă o mare parte din același teren, am găsit-o destul de accesibilă decât s hârtia Goldberg . De asemenea, mi s-a părut mai ușor să înțeleg părțile mai complexe ale lucrării după ce am citit articolele anterioare ale lui Richards și după aceste articole timpurii, Richard se separă în multe zone interesante care nu au fost atinse de lucrarea Goldberg.

Așa cum astfel a vorbit ak menționat în comentarii:

În calitate de autor al articolele pe care aș dori să le menționez că am creat versiuni interactive ale acestora pe blogul meu www.thusspakeak.com începând cu thusspakeak.com/ak/2013/06 .

Comentarii

• În calitate de autor al acestor articole, ‘ aș dori să menționez că am creat versiuni interactive ale acestora pe blogul meu www.thusspakeak.com începând cu thusspakeak.com/ak/2013/06 .
• Mulțumesc @ thusspakea.k. Am ‘ am adăugat o notă la răspunsul meu și tho elementele interactive funcționează foarte frumos.

Ei bine, thorsten are linkul definitiv . Aș adăuga:

Orice formă de reprezentare va avea o eroare de rotunjire pentru un anumit număr. Încercați să exprimați 1/3 în virgulă mobilă IEEE sau în zecimal. Niciunul dintre ei nu o poate face cu precizie. Acest lucru merge dincolo de răspunsul la întrebarea dvs., dar am folosit cu succes această regulă:

• Stocați valorile introduse de utilizator în zecimal (deoarece aproape sigur au introdus-o într-o reprezentare zecimală – foarte puțini utilizatori va folosi binar sau hex). În acest fel, aveți întotdeauna reprezentarea exactă introdusă de utilizator.
• Dacă trebuie să stocați fracțiile introduse de utilizator, stocați numeratorul și numitorul (de asemenea, în zecimal)
• Dacă aveți un sistem cu mai multe unități de măsură pentru aceeași cantitate (cum ar fi Celsius / Fahrenheit), iar utilizatorul poate introduce ambele, stoca valoarea introdusă și unitățile în care le-a introdus. Nu încercați să convertiți și să salvați ca o singură reprezentare, cu excepția cazului în care o puteți face fără pierderea preciziei / preciziei. Utilizați valoarea stocată și unitățile în toate calculele.
• Stocați valorile generate de mașină în virgulă mobilă IEEE (acestea pot fi numerele generate de un dispozitiv electronic de măsurare, cum ar fi un senzor analogic cu un convertor A / D, sau rezultatul netrondit al unui calcul). Rețineți că acest lucru nu se aplică dacă citiți un senzor printr-o conexiune serială și deja oferă vă valoarea într-un format zecimal (de exemplu, 18,2 C).
• Stocați totaluri vizibile de utilizator etc., în zecimal (cum ar fi un cont bancar echilibru). Rotunjiți în mod corespunzător, dar folosiți acea valoare ca valoare definitivă pentru toate calculele viitoare.

Comentarii

• Aș adăuga: luați în considerare utilizarea unui pachetul matematic de precizie arbitrară, cum ar fi ARPREC sau decNumber.
• Nu ‘ t zecimal (spre deosebire de binar) are multe beneficii pentru valorile întregi, cum ar fi numeratorul și numitorul unei fracții. Oricare poate stoca valori întregi exacte, iar binarul este mai eficient. Există ‘ un anumit cost în conversia înainte și înapoi pentru intrare și ieșire, dar ‘ este probabil înundat de costul fizic efectuarea I / O.

Ceea ce pare să nu fi fost menționat până acum sunt conceptele unui algoritm instabil și o problemă necondiționată . Mă voi adresa întâi la primul, deoarece acesta pare a fi o capcană mai frecventă pentru numericienii novici.

Luați în calcul calculul puterilor raportului auriu (reciproc) φ=0.61803…; o modalitate posibilă de a face acest lucru este utilizarea formulei recursive φ^n=φ^(n-2)-φ^(n-1), începând cu φ^0=1 și φ^1=φ. Dacă executați această recursivitate în mediul dvs. de calcul preferat și comparați rezultatele cu puteri evaluate cu exactitate, veți găsi o eroziune lentă a cifrelor semnificative. Iată ce se întâmplă, de exemplu, în 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} 

Rezultatul presupus pentru φ^41 are semnul greșit și chiar mai devreme, valorile calculate și reale pentru φ^39 nu au în comun cifre (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Algoritmul este astfel instabil și nu ar trebui să utilizați această formulă de recursivitate în aritmetică inexactă. Acest lucru se datorează natura inerentă a formulei recursive: există o soluție „în descompunere” și „în creștere” la această recursiune și încercarea de a calcula soluția „în descompunere” prin soluție directă atunci când există o soluție alternativă „în creștere” este cererea de durere numerică. Astfel, ar trebui să ne asigurăm că algoritmii lui numerici sunt stabili.

Acum, în ceea ce privește conceptul de problemă prost condiționată : chiar dacă poate exista o modalitate stabilă de a face ceva numeric, ar putea fi foarte bine că problema pe care o ai pur și simplu nu pot fi rezolvate de algoritmul dvs. Aceasta este vina problemei în sine și nu metoda soluției. Exemplul canonic în numerică este soluția ecuațiilor liniare care implică așa-numita „matrice Hilbert”:

matricea este exemplul canonic al unei matrici prost condiționate : încercarea de a rezolva un sistem cu o matrice Hilbert mare ar putea returna o soluție inexactă.

Aici „sa Mathematica demonstrație: comparați rezultatele aritmeticii exacte

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

și a aritmeticii inexacte

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

(Dacă ați încercat-o în Mathematica , veți observa câteva mesaje de eroare care avertizează despre apariția unor condiții nefavorabile.)

În ambele cazuri, pur și simplu creșteți precizia nu este un remediu; nu va face decât să întârzie erodarea inevitabilă a figurilor.

Iată cu ce s-ar putea să vă confruntați. Soluțiile ar putea fi dificile: pentru prima, fie vă întoarceți la planșă, fie vă plimbați prin jurnale / cărți / orice să găsiți dacă altcineva a venit cu o soluție mai bună decât ați; pentru al doilea, fie renunți, fie îți reformulezi problema cu ceva mai tratabil.

Vă voi lăsa un citat din Dianne O „Leary:

Viața ne poate arunca unele probleme prost condiționate, dar nu există motive întemeiate să ne mulțumim cu un algoritm instabil.

deoarece numerele zecimale de bază 10 nu pot fi exprimate în baza 2

sau cu alte cuvinte 1/10 nu poate fi transformat într-o fracție cu o putere de 2 în numitor (care este ceea ce sunt în esență numerele cu virgulă mobilă)

Comentarii

• Nu tocmai adevărat: 0,5 și 0,25 pot fi exprimate în baza 2. Cred că vrei să spui ” nu toate numerele zecimale de bază 10 „.
• Mai precis. Nu toate numerele fracționare pot fi reprezentate exact folosind o notație în virgulă mobilă (adică cu. Atât baza 2, cât și baza 10 au această problemă exactă). Încercați și faceți 9*3.3333333 în zecimal și începeți-l la 9*3 1/3
• Aceasta este cea mai comună sursă de virgulă mobilă confuzie. .1 + .1 != .2 deoarece se utilizează codarea binară în virgulă mobilă, nu zecimală.
• @SeanMcMillan: Și 1.0/3.0*3.0 != 1.0, deoarece flotant se utilizează codarea binară a punctelor, nu trinară.

În matematică, există infinit de multe numere raționale . O variabilă pe 32 de biți poate avea doar 2 ³² valori diferite și o variabilă pe 64 de biți numai 2 valori 64 . Prin urmare, există infinit de multe numere raționale care nu au o reprezentare precisă.

Am putea veni cu scheme care ne-ar permite să reprezentăm 1/3 perfect sau 1/100. Se pare că, în multe scopuri practice, acest lucru nu este foarte util. Există o mare excepție: în finanțe, fracțiile zecimale apar adesea. Asta se întâmplă mai ales pentru că finanța este în esență o activitate umană, nu una fizică.

Prin urmare, de obicei alegem să folosim virgulă mobilă binară și rotunjim orice valoare care nu poate fi reprezentată în binar. Dar în finanțe, uneori alegem virgula mobilă zecimală și rotunjim valorile la cea mai apropiată valoare zecimală .

Comentarii

• Chiar mai rău, în timp ce o cantitate infinită (infinit de infinită) de memorie i-ar permite să reprezinte toate raționalele, nu ar este suficient pentru reprezentarea realilor. Și mai rău încă, aproape toate numerele reale nu sunt numere computabile. Cel mai bun lucru pe care îl putem face cu o cantitate finită de memorie este de a aproxima un subset al intervalului finit al realilor.
• @Kevin: ‘ vorbești despre numerele calculabile, care este un subset mic (un subset cu măsura zero) al realilor.
• +1 pentru cea mai de bază explicație: ‘ încercați să reprezentați o cantitate infinită de numere cu un număr finit de biți.
• @DavidHammen: numerele calculate pot fi un subset mic ( de măsură zero) a realilor – dar fiecare număr cu care ‘ veți lucra vreodată într-un program este, prin definiție, calculabil.
• @Giorgio: Dacă alegeți reprezentarea potrivită, rădăcina pătrată a lui 2 este reprezentabilă, de exemplu, ca șir "√2". (Vechiul meu calculator HP-48 a reușit să facă exact acest lucru, iar măsurarea acestei valori a dus exact la 2.0.) Există doar o infinitate de numere reale reprezentabile pentru orice reprezentare finită – dar nici un calcul nu poate produce un număr care nu este, în principiu, reprezentabil. În practică, virgula mobilă binară limitează drastic setul de numere reprezentabile, cu avantajul vitezei aprinse și a stocării minuscule în raport cu reprezentările simbolice.

singura „problemă de rotunjire” cu adevărat evidentă cu numere în virgulă mobilă despre care cred că este cu filtre medii mobile:

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

pentru a face acest lucru fără acumularea zgomotului, doriți să vă asigurați că $ x [n] $ pe care îl adăugați în mostrele curente este exact același cu $ x [nN] $, veți scădea probele de $ N $ în viitor. dacă nu este, atunci ceea ce este diferit este un mic turd care se blochează în linia de întârziere și nu va ieși niciodată. asta pentru că acest filtru mediu mobil este de fapt construit cu un IIR care are un pol marginal stabil la $ z = 1 $ și un zero care îl anulează în interior. dar este un integrator și orice porcărie care se integrează și nu se elimină în întregime va exista în suma integratorului pentru totdeauna. Aici punctul fix nu are aceeași problemă pe care o au numerele cu virgulă mobilă.

Comentarii

• hei, nu ‘ t $ LaTeX $ marcă matematică în forumul prog.SE ??? că ‘ e foarte șchiop dacă nu ‘ t.
• Consultați aceasta pe meta.SO și întrebări legate