Cosa causa errori di arrotondamento in virgola mobile?

Questo perché alcune frazioni richiedono una quantità molto grande (o addirittura infinita) di posizioni per essere espresse senza arrotondamenti. Questo vale sia per la notazione decimale che per quella binaria o qualsiasi altra. Se limitassi la quantità di cifre decimali da utilizzare per i tuoi calcoli (ed evitassi di fare calcoli in notazione frazionaria), dovresti arrotondare anche unespressione semplice come 1/3 + 1/3. Invece di scrivere 2/3 come risultato dovresti scrivere 0.33333 + 0.33333 = 0.66666 che non è identico a 2/3.

Nel caso di un computer il numero di cifre è limitato dalla natura tecnica della sua memoria e dei registri della CPU. La notazione binaria utilizzata internamente aggiunge qualche difficoltà in più. I computer normalmente non possono esprimere numeri in notazione frazionaria, sebbene alcuni linguaggi di programmazione aggiungano questa capacità, che consente di evitare tali problemi in una certa misura.

Quello che ogni informatico dovrebbe sapere sullaritmetica in virgola mobile

Commenti

• Spot on. Ma vorrei anche notare che alcuni numeri che terminare in decimale don ‘ t terminare in binario. In particolare 0.1 è un numero ricorrente in binario e quindi nessun numero binario in virgola mobile può rappresentare esattamente 0.1.
• Floating i punti non sono ‘ t utile solo per molte cifre decimali. Gli interi a 32 bit possono contare solo fino a circa 4 miliardi, ma un float a 32 bit può essere quasi infinitamente grande.
• In particolare, le frazioni che possiamo esprimere come decimali finiti sono quelle i cui denominatori ‘ la scomposizione in fattori primi contiene solo 2 e 5 (es. possiamo esprimere 3/10 e 7/25 , ma no 11/18). Quando passiamo al binario, perdiamo il fattore 5, in modo che solo i razionali diadici (es. 1/4, 3/128) possano essere espressi esattamente.

Principalmente, gli errori di arrotondamento derivano dal fatto che linfinito di tutti i numeri reali non può essere rappresentato dalla memoria finita di un computer , per non parlare di una piccola porzione di memoria come una singola variabile a virgola mobile , quindi molti numeri memorizzati sono solo approssimazioni del numero che intendono rappresentare.

Poiché esiste solo un numero limitato di valori che non sono unapprossimazione e qualsiasi operazione tra unapprossimazione e un altro numero risulta in unapprossimazione, gli errori di arrotondamento sono quasi inevitabili .

Limportante cosa è rendersi conto di quando è probabile che causino un problema e adottare misure per mitigare i rischi .

Oltre a David Goldberg “s What Every Computer Scientis t Should Know About Floating-Point Arithmetic (ripubblicato da Sun / Oracle come appendice al loro Numerical Computation Guide ), menzionata da thorsten , ACCU journal Sovraccarico ha pubblicato uneccellente serie di articoli di Richard Harris sul Floating Point Blues .

La serie è iniziata con

• Dovrai pensarci! in Sovraccarico n. 99 ( pdf , p5-10):

Co numerico Il mputing ha molte insidie. Richard Harris inizia a cercare un proiettile dargento.

Il drago dellerrore numerico non viene spesso risvegliato dal suo sonno, ma se affrontato incautamente infliggerà occasionalmente danni catastrofici ai calcoli del programmatore incauto.

Tanto che alcuni programmatori, essendosi imbattuti in lui nelle foreste dellaritmetica in virgola mobile IEEE 754, sconsigliano i loro compagni di viaggiare in quel bel paese.

In questa serie di articoli esploreremo il mondo del calcolo numerico, contrapponendo laritmetica in virgola mobile ad alcune delle tecniche che sono state proposte come sostituti più sicuri. Impareremo che il territorio del drago è davvero di vasta portata e che in generale dobbiamo procedere con cautela se temiamo il suo unattenzione devastante.

Richard inizia spiegando la tassonomia dei numeri reali, razionale, irrazionale, algebrica e trascendentale. Poi prosegue spiegando la rappresentazione IEEE754, prima di passare allerrore di cancellazione e ai problemi di ordine di esecuzione.

Se non leggi più a fondo, avrai unottima base nei problemi associati ai numeri in virgola mobile .

Se vuoi saperne di più, tuttavia, continua con

• Perché Fixed Point Won” t Cure Your Floating Point Blues in Sovraccarico n. 100 ( pdf , pagg. 15-22)
• Perché Rationals non lo farà Cure Your Floating Point Blues in Overload # 101 ( pdf , pagg. 9-13)
• Perché lalgebra del computer non cura il tuo blues in virgola mobile in Sovraccarico # 102 ( pdf , p9- 14).
• Perché laritmetica a intervalli non curerà il tuo blues in virgola mobile in Sovraccarico 103 ( pdf , pagg. 19-24)

Passa quindi a cercare di aiutarti a curare il tuo Calculus Blues

• Perché [Inserisci lalgoritmo qui] non curerà il tuo calcolo blues in Sovraccarico 104 ( pdf , pagg. 22-24).
• Perché le differenze finite non risolveranno il tuo calcolo blues in Sovraccarico 105 ( pdf , p5-12).
• Perché lapprossimazione polinomiale non “t Cure Your Calculus Blues in Sovraccarico 106 ( pdf , pagg. 16-25).
• Perché lalgebra del computer non cura il tuo calcolo blues in Sovraccarico 107 ( pdf , pagg. 15-20).

e, ultimo ma non meno importante, cè

• Perché la differenziazione automatica non risolverà la malinconia del calcolo in Sovraccarico 108 ( pdf , p4-11).

Lintera serie di articoli è vale la pena esaminarle e, con un totale di 66 pagine, sono ancora più piccole delle 77 pagine del documento di Goldberg .

Mentre questo series copre gran parte dello stesso terreno, lho trovato piuttosto più accessibile del paper di Goldberg. Ho anche trovato più facile capire le parti più complesse del documento dopo aver letto il primo degli articoli di Richards e dopo quei primi articoli, Richard si dirama in molte aree interessanti non toccate dallarticolo di Goldberg.

Come così spake ak menzionato nei commenti:

Come autore di quegli articoli che “vorrei menzionare che ne ho creato versioni interattive sul mio blog www.thusspakeak.com che iniziano con thusspakeak.com/ak/2013/06 .

Commenti

• In qualità di autore di questi articoli, ‘ vorrei menzionare che ne ho creato versioni interattive sul mio blog www.thusspakeak.com che iniziano con thusspakeak.com/ak/2013/06 .
• Grazie @ thusspakea.k. ‘ ho aggiunto una nota alla mia risposta, e comunque se gli elementi interattivi funzionano molto bene.

Bene, thorsten ha il link definitivo. Aggiungerei:

Qualsiasi forma di rappresentazione avrà qualche errore di arrotondamento per qualche numero. Prova a esprimere 1/3 in virgola mobile IEEE o in decimale. Nessuno dei due può farlo con precisione. Questo va oltre la risposta alla tua domanda, ma ho utilizzato questa regola pratica con successo:

• Memorizza i valori inseriti dallutente in decimali (perché quasi certamente li hanno inseriti in una rappresentazione decimale – pochissimi utenti utilizzerà binario o esadecimale). In questo modo avrai sempre la rappresentazione esatta inserita dallutente.
• Se devi memorizzare le frazioni inserite dallutente, memorizza il numeratore e il denominatore (anche in decimale)
• Se hai un sistema con più unità di misura per la stessa quantità (come Celsius / Fahrenheit), e lutente può inserire entrambi, memorizzare il valore che ha inserito e le unità in cui le ha inserite. Non provare a convertire e salvare come una singola rappresentazione, a meno che tu non possa farlo senza perdita di precisione / accuratezza. Utilizza il valore memorizzato e unità in tutti i calcoli.
• Memorizza i valori generati dalla macchina in virgola mobile IEEE (possono essere numeri generati da un dispositivo di misurazione elettronico, come un sensore analogico con un convertitore A / D, o il risultato non arrotondato di un calcolo). Si noti che questo non si applica se si sta leggendo un sensore tramite una connessione seriale e sta già dando il valore in un formato decimale (ad esempio 18.2 C).
• Memorizza i totali visualizzabili dallutente, ecc., in decimale (come un conto bancario equilibrio). Arrotonda in modo appropriato, ma usa quel valore come valore definitivo per tutti i calcoli futuri.

Commenti

• Vorrei aggiungere: considera lutilizzo di un pacchetto matematico a precisione arbitraria come ARPREC o decNumber.
• Non ‘ t decimale (al contrario di binario) ha molti vantaggi per i valori interi, come il numeratore e denominatore di una frazione. Entrambi possono memorizzare valori interi esatti e binary è più efficiente. ‘ è un po di costo nella conversione avanti e indietro per input e output, ma è probabile che ‘ sia sommerso dal costo di eseguire lI / O.

Ciò che sembra non essere stato menzionato finora sono i concetti di un algoritmo instabile e un problema mal condizionato . Affronterò prima il primo, in quanto sembra essere una trappola più frequente per i numericisti alle prime armi.

Considera il calcolo dei poteri della sezione aurea (reciproca) φ=0.61803…; un modo possibile per farlo è utilizzare la formula di ricorsione φ^n=φ^(n-2)-φ^(n-1), che inizia con φ^0=1 e φ^1=φ. Se esegui questa ricorsione nel tuo ambiente di elaborazione preferito e confronti i risultati con potenze accuratamente valutate, troverai una lenta erosione di cifre significative. Ecco cosa accade ad esempio 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} 

Il presunto risultato di φ^41 ha il segno sbagliato e, anche prima, i valori calcolati ed effettivi per φ^39 non condividono cifre in comune (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Lalgoritmo è quindi instabile e non si dovrebbe utilizzare questa formula di ricorsione in aritmetica inesatta. la natura intrinseca della formula della ricorsione: cè una soluzione “decadente” e “crescente” a questa ricorsione, e cercare di calcolare la soluzione “decadente” con una soluzione diretta quando cè una soluzione alternativa “crescente” è implorare dolore numerico. Uno dovrebbe quindi assicurarsi che i suoi algoritmi numerici siano stabili.

Ora, passiamo al concetto di un problema mal condizionato : anche se potrebbe esserci un modo stabile per farlo numericamente, potrebbe benissimo essere che il problema tu abbia semplicemente non possono essere risolti dal tuo algoritmo. Questa è colpa del problema stesso e non del metodo di soluzione. Lesempio canonico in numerico è la soluzione di equazioni lineari che coinvolgono la cosiddetta “matrice di Hilbert”:

La matrix è lesempio canonico di una matrice mal condizionata : provare a risolvere un sistema con una grande matrice di Hilbert potrebbe restituire una soluzione imprecisa.

Qui “sa Mathematica dimostrazione: confronta i risultati dellaritmetica esatta

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

e dellaritmetica inesatta

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

(Se lhai provato in Mathematica , noterai alcuni messaggi di errore che avvisano della comparsa del mal condizionamento.)

In entrambi i casi, semplicemente aumentando il la precisione non è una cura; ritarderà solo linevitabile erosione delle cifre.

Questo è ciò che potresti dover affrontare. Le soluzioni potrebbero essere difficili: per la prima, o torni al tavolo da disegno, o guadagni diari / libri / qualunque cosa per trovare se qualcun altro ha trovato una soluzione migliore di te; per il secondo, o ti arrendi o riformuli il tuo problema in qualcosa di più trattabile.

Ti lascio con una citazione di Dianne O “Leary:

La vita potrebbe crearci dei problemi mal condizionati, ma non ci sono buone ragioni per accontentarsi di un algoritmo instabile.

perché i numeri decimali in base 10 non possono essere espressi in base 2

o in altre parole non può essere 1/10 trasformato in una frazione con una potenza di 2 nel denominatore (che è ciò che sono essenzialmente i numeri in virgola mobile)

Commenti

• Non esattamente vero: 0,5 e 0,25 può essere espresso in base 2. Penso che tu intenda ” non tutti i numeri decimali in base 10 “.
• Più precisamente. Non tutti i numeri frazionari possono essere rappresentati esattamente usando una notazione in virgola mobile (cioè con. Sia la base 2 che la base 10 hanno questo problema esatto). Prova a eseguire 9*3.3333333 in decimale e inseriscilo in 9*3 1/3
• Questa è la fonte più comune di virgola mobile confusione. .1 + .1 != .2 perché viene utilizzata la codifica binaria a virgola mobile, non decimale.
• @SeanMcMillan: e 1.0/3.0*3.0 != 1.0, perché mobile -point viene utilizzata la codifica binaria, non trinaria.

In matematica, ci sono infiniti numeri razionali . Una variabile a 32 bit può avere solo 2 valori ³² diversi e una variabile a 64 bit solo 2 valori ⁶⁴ . Pertanto, ci sono infiniti numeri razionali che non hanno una rappresentazione precisa.

Potremmo escogitare schemi che ci permettano di rappresentare perfettamente 1/3 o 1/100. Si scopre che per molti scopi pratici questo non è molto utile. Cè una grande eccezione: in finanza, le frazioni decimali spesso compaiono. Questo è principalmente perché la finanza è essenzialmente unattività umana, non fisica.

Pertanto, di solito scegliamo di utilizzare la virgola mobile binaria e arrotondiamo qualsiasi valore che non può essere rappresentato in binario. Ma in finanza, a volte scegliamo il punto mobile decimale e arrotondiamo i valori al valore decimale più vicino .

Commenti

• Ancora peggio, mentre una quantità di memoria infinita (numerabilmente infinita) consentirebbe di rappresentare tutti i razionali, non lo farebbe è sufficiente per rappresentare i reali. Ancora peggio ancora, quasi tutti i numeri reali non sono numeri calcolabili. Il meglio che possiamo fare con una quantità finita di memoria è approssimare un sottoinsieme di intervalli finiti dei reali.
• @Kevin: ‘ stai parlando dei numeri calcolabili, che è un piccolo sottoinsieme (un sottoinsieme con misura zero) dei reali.
• +1 per il spiegazione più semplice: ‘ stai cercando di rappresentare una quantità infinita di numeri con un numero finito di bit.
• @DavidHammen: i numeri calcolabili sono un piccolo sottoinsieme ( di misura zero) dei reali – ma ogni numero con cui ‘ lavorerai mai in un programma è, per definizione, calcolabile.
• @Giorgio: If scegli la rappresentazione corretta, la radice quadrata di 2 è rappresentabile, ad esempio, come la stringa "√2". (La mia vecchia calcolatrice HP-48 era in grado di fare esattamente questo, e il quadrato di quel valore ha prodotto esattamente 2.0.) Cè solo uninfinità numerabile di numeri reali rappresentabili per qualsiasi rappresentazione finita – ma nessun calcolo può produrre un numero che non è, in linea di principio, rappresentabile. In pratica, la virgola mobile binaria limita drasticamente linsieme dei numeri rappresentabili, con il vantaggio di una velocità incredibile e di una memoria ridotta rispetto alle rappresentazioni simboliche.

lunico “problema di arrotondamento” veramente ovvio con i numeri in virgola mobile a cui penso è con i filtri della media 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} $$

per farlo funzionare senza laccumulo di rumore, vuoi assicurarti che $ x [n] $ che aggiungi nei campioni correnti sia esattamente lo stesso di $ x [nN] $ che sottrai $ N $ campioni in futuro. se non lo è, allora ciò che è diverso è un piccolo stronzo che si blocca nella tua linea di ritardo e non uscirà mai. questo perché questo filtro a media mobile è effettivamente costruito con un IIR che ha un polo marginalmente stabile a $ z = 1 $ e uno zero che lo annulla allinterno. ma è un integratore e qualsiasi schifezza che viene integrata e non completamente rimossa esisterà per sempre nella somma dellintegratore. Questo è dove il punto fisso non ha lo stesso problema dei numeri in virgola mobile.

Commenti

• hey, non ‘ t $ LaTeX $ markup matematico funziona nel forum prog.SE ??? che ‘ è davvero noioso se non ‘ t.
• Vedi questo su meta.SO e domande collegate