Domanda La matematica in virgola mobile è rotta?


Considera il seguente codice:

0.1 + 0.2 == 0.3  ->  false
0.1 + 0.2         ->  0.30000000000000004

Perché si verificano queste inesattezze?


2259
2018-02-25 21:39


origine


risposte:


Binario virgola mobile la matematica è così. Nella maggior parte dei linguaggi di programmazione, è basato sul Standard IEEE 754. JavaScript utilizza la rappresentazione in virgola mobile a 64 bit, che è la stessa di Java double. Il nodo del problema è che i numeri sono rappresentati in questo formato come un numero intero moltiplicato per una potenza di due; numeri razionali (come 0.1, che è 1/10) il cui denominatore non è un potere di due non può essere esattamente rappresentato.

Per 0.1 nella norma binary64 formato, la rappresentazione può essere scritta esattamente come

  • 0.1000000000000000055511151231257827021181583404541015625 in decimale, o
  • 0x1.999999999999ap-4 in Notazione hexfloat C99.

Al contrario, il numero razionale 0.1, che è 1/10, può essere scritto esattamente come

  • 0.1 in decimale, o
  • 0x1.99999999999999...p-4 in un analogo della notazione hexfloat C99, dove il ... rappresenta una sequenza infinita di 9.

Le costanti 0.2 e 0.3 nel tuo programma saranno anche le approssimazioni ai loro veri valori. Succede che il più vicino double a 0.2 è più grande del numero razionale 0.2 ma quello il più vicino double a 0.3 è più piccolo del numero razionale 0.3. La somma di 0.1 e 0.2 finisce per essere più grande del numero razionale 0.3 e quindi in disaccordo con la costante nel codice.

Lo è un trattamento abbastanza completo di questioni aritmetiche in virgola mobile Quello che ogni scienziato informatico dovrebbe sapere sull'aritmetica virgola mobile. Per una spiegazione più facile da digerire, vedi floating-point-gui.de.


1718
2018-04-18 11:52



Prospettiva di un progettista hardware

Credo che dovrei aggiungere la prospettiva di un progettista hardware a questo dato che progetto e costruisco hardware in virgola mobile. Conoscere l'origine dell'errore può aiutare a capire cosa sta accadendo nel software e, alla fine, spero che questo aiuti a spiegare i motivi per cui gli errori in virgola mobile si verificano e sembrano accumularsi nel tempo.

1. Panoramica

Da un punto di vista ingegneristico, la maggior parte delle operazioni in virgola mobile avrà qualche elemento di errore dal momento che l'hardware che esegue i calcoli in virgola mobile ha solo bisogno di avere un errore inferiore alla metà di una unità nell'ultimo posto. Pertanto, molto hardware si fermerà con una precisione che è necessaria solo per produrre un errore inferiore alla metà di una unità nell'ultimo posto per un singola operazione che è particolarmente problematico nella divisione in virgola mobile. Ciò che costituisce una singola operazione dipende dal numero di operandi che l'unità assume. Per la maggior parte, è due, ma alcune unità richiedono 3 o più operandi. Per questo motivo, non vi è alcuna garanzia che le operazioni ripetute generino un errore desiderabile poiché gli errori si sommano nel tempo.

2. Standard

La maggior parte dei processori segue il IEEE-754 standard ma alcuni usano standard denormalizzati o diversi . Ad esempio, in IEEE-754 esiste una modalità denormalizzata che consente la rappresentazione di numeri in virgola mobile molto piccoli a scapito della precisione. Quanto segue, tuttavia, coprirà la modalità normalizzata di IEEE-754, che è la modalità di funzionamento tipica.

Nello standard IEEE-754, ai progettisti di hardware è consentito qualsiasi valore di errore / epsilon purché sia ​​inferiore alla metà di una unità nell'ultimo posto e il risultato deve essere inferiore alla metà di un'unità nell'ultimo posto per una operazione. Questo spiega perché quando ci sono operazioni ripetute, gli errori si sommano. Per la doppia precisione IEEE-754, questo è il 54 ° bit, poiché 53 bit sono usati per rappresentare la parte numerica (normalizzata), detta anche mantissa, del numero in virgola mobile (ad esempio la 5.3 in 5.3e5). Le sezioni successive descrivono più in dettaglio le cause dell'errore hardware su varie operazioni in virgola mobile.

3. Causa dell'errore di arrotondamento nella divisione

La causa principale dell'errore nella divisione in virgola mobile è rappresentata dagli algoritmi di divisione utilizzati per calcolare il quoziente. La maggior parte dei sistemi informatici calcola la divisione usando la moltiplicazione per inverso, principalmente in Z=X/Y, Z = X * (1/Y). Una divisione è calcolata iterativamente, cioè ogni ciclo calcola alcuni bit del quoziente fino a raggiungere la precisione desiderata, che per IEEE-754 è qualsiasi cosa con un errore inferiore a un'unità nell'ultimo posto. La tabella dei reciproci di Y (1 / Y) è nota come la tabella di selezione del quoziente (QST) nella divisione lenta e la dimensione in bit della tabella di selezione del quoziente è solitamente la larghezza della radice o un numero di bit di il quoziente calcolato in ogni iterazione, più alcuni bit di guardia. Per lo standard IEEE-754, a doppia precisione (64 bit), sarebbe la dimensione della radice del divisore, più alcuni bit di guardia k, dove k>=2. Quindi, ad esempio, una tabella di selezione del quoziente tipica per un divisore che calcola 2 bit del quoziente alla volta (radice 4) sarebbe 2+2= 4 bit (più alcuni bit opzionali).

3.1 Arrotondamento divisione: approssimazione del reciproco

Quali sono i reciproci nella tabella di selezione dei quozienti dipendono dal metodo di divisione: divisione lenta come la divisione SRT o divisione veloce come la divisione Goldschmidt; ogni voce viene modificata in base all'algoritmo di divisione nel tentativo di ottenere l'errore più basso possibile. In ogni caso, però, tutti i reciproci sono approssimazioni dell'effettivo reciproco e introdurre qualche elemento di errore. Sia la divisione lenta che i metodi di divisione rapida calcolano il quoziente in modo iterativo, ovvero un numero di bit del quoziente viene calcolato ogni passo, quindi il risultato viene sottratto dal dividendo e il divisore ripete i passaggi finché l'errore non è inferiore alla metà di uno unità nell'ultimo posto. I metodi di divisione lenti calcolano un numero fisso di cifre del quoziente in ogni passaggio e sono in genere meno costosi da compilare, mentre i metodi di divisione rapida calcolano un numero variabile di cifre per passo e sono solitamente più costosi da costruire. La parte più importante dei metodi di divisione è che la maggior parte di essi si basa su ripetute moltiplicazioni per a approssimazione di un reciproco, quindi sono inclini all'errore.

4. Errori di arrotondamento in altre operazioni: troncamento

Un'altra causa degli errori di arrotondamento in tutte le operazioni sono le diverse modalità di troncamento della risposta finale consentita da IEEE-754. C'è un troncamento, round-to-zero, round-to-closest (predefinito), round-down e round-up. Tutti i metodi introducono un elemento di errore di meno di un'unità nell'ultimo posto per una singola operazione. Nel tempo e nelle operazioni ripetute, il troncamento aggiunge anche cumulativamente all'errore risultante. Questo errore di troncamento è particolarmente problematico in esponenziazione, il che implica una qualche forma di moltiplicazione ripetuta.

5. Operazioni ripetute

Poiché l'hardware che esegue i calcoli in virgola mobile deve solo fornire un risultato con un errore inferiore alla metà di un'unità nell'ultimo posto per una singola operazione, l'errore aumenterà per le operazioni ripetute se non viene osservato. Questo è il motivo per cui nei calcoli che richiedono un errore limitato, i matematici usano metodi come l'uso del round to to nearest anche digit nell'ultimo posto di IEEE-754, perché, nel tempo, è più probabile che gli errori si annullino a vicenda, e Intervallo aritmetico combinato con variazioni del Modalità di arrotondamento IEEE 754 per prevedere gli errori di arrotondamento e correggerli. A causa del suo basso errore relativo rispetto alle altre modalità di arrotondamento, arrotondando alla cifra pari più vicina (nell'ultimo posto), è la modalità di arrotondamento predefinita di IEEE-754.

Si noti che la modalità di arrotondamento predefinita, da rotonda a più vicina anche digit nell'ultimo posto, garantisce un errore inferiore alla metà di un'unità nell'ultimo posto per un'operazione. L'utilizzo del troncamento, del round-up e del round down da solo può causare un errore superiore alla metà di un'unità nell'ultimo posto, ma inferiore a un'unità nell'ultimo posto, quindi queste modalità non sono consigliate a meno che non siano usato in Aritmetica a intervalli.

6. Riepilogo

In breve, la ragione fondamentale per gli errori nelle operazioni in virgola mobile è una combinazione del troncamento nell'hardware e il troncamento di un reciproco nel caso della divisione. Poiché lo standard IEEE-754 richiede solo un errore inferiore alla metà di una unità nell'ultimo posto per una singola operazione, gli errori in virgola mobile su operazioni ripetute si sommano se non vengono corretti.


490
2018-02-25 21:43



Quando converti .1 o 1/10 in base 2 (binario) ottieni un pattern ripetuto dopo il punto decimale, proprio come provare a rappresentare 1/3 in base 10. Il valore non è esatto, e quindi non puoi fare matematica esatta con esso utilizzando i normali metodi in virgola mobile.


356
2017-11-20 02:39



La maggior parte delle risposte qui affronta questa domanda in termini tecnici molto asciutti. Mi piacerebbe affrontare questo in termini che i normali esseri umani possono capire.

Immagina di provare a tagliare le pizze. Hai una taglierina robotica che può tagliare fette di pizza Esattamente a metà. Può dimezzare un'intera pizza o dimezzare una fetta esistente, ma in ogni caso il dimezzamento è sempre esatto.

Quella taglierina della pizza ha movimenti molto sottili, e se inizi con una pizza intera, poi dimezzala e continua a dimezzare la fetta più piccola ogni volta, puoi dimezzare 53 volte prima che la fetta sia troppo piccola anche per le sue abilità di alta precisione. A quel punto, non puoi più dimezzare quella fetta molto sottile, ma devi includerla o escluderla così com'è.

Ora, come raccoglieresti tutte le fette in modo tale da aggiungere fino a un decimo (0,1) o un quinto (0,2) di una pizza? Pensaci davvero e prova a risolverlo. Puoi anche provare ad usare una vera pizza, se hai una mitica tagliapizza di precisione a portata di mano. :-)


I programmatori più esperti, ovviamente, conoscono la vera risposta, che è che non c'è modo di ricostruire insieme esatto decimo o quinto della pizza che usa quelle fette, non importa quanto finemente le affili. Si può fare un'approssimazione abbastanza buona, e se si sommano l'approssimazione di 0.1 con l'approssimazione di 0.2, si ottiene un'approssimazione abbastanza buona di 0.3, ma è pur sempre solo un'approssimazione.

Per i numeri a precisione doppia (che è la precisione che permette di dimezzare la vostra pizza 53 volte), il numero immediatamente inferiore e superiore a 0,1 sono 0,09999999999999999167332731531132594682276248931884765625 e 0,1000000000000000055511151231257827021181583404541015625. Quest'ultimo è un po 'più vicino a 0.1 rispetto al primo, quindi un parser numerico, dato un input di 0.1, preferirebbe quest'ultimo.

(La differenza tra questi due numeri è la "fetta" più piccolo che dobbiamo deciderà se includere, che introduce una polarizzazione verso l'alto, o escludere, che introduce una distorsione verso il basso. Il termine tecnico per quella piccola fetta è un ulp.)

Nel caso di 0.2, i numeri sono tutti uguali, appena scalati di un fattore 2. Di nuovo, preferiamo il valore leggermente superiore a 0,2.

Si noti che in entrambi i casi, le approssimazioni per 0.1 e 0.2 hanno una leggera tendenza verso l'alto. Se aggiungiamo abbastanza di questi pregiudizi, in cui saranno spingere il numero sempre più lontano da quello che vogliamo, e infatti, nel caso di 0.1 + 0.2, la distorsione è abbastanza alto che il numero risultante non è più il numero più vicino a 0,3.

In particolare, 0,1 + 0,2 è in realtà 0,1000000000000000055511151231257820121181583404541015625 + 0,200000000000000011102230246251565404236316680908203125 = 0,3000000000000000444089209850062616169452667236328125, mentre il numero più vicino a 0,3 è in realtà 0,299999999999999988897769753748434595763683319091796875.


Post scriptum Alcuni linguaggi di programmazione forniscono anche frese per la pizza che possono dividere le fette in decimi esatti. Sebbene tali tagliapiastrelle siano rari, se ne avete accesso a uno, dovreste usarlo quando è importante essere in grado di ottenere esattamente un decimo o un quinto di una fetta.

(Originariamente pubblicato su Quora.)


225
2018-02-25 21:41



Errori di arrotondamento a virgola mobile. 0.1 non possono essere rappresentati con la massima precisione in base 2 come nella base 10 a causa del fattore primo mancante di 5. Così come 1/3 prende un numero infinito di cifre per rappresentare in decimale, ma è "0,1" in base-3, 0.1 prende un numero infinito di cifre in base-2 dove non è in base-10. E i computer non hanno una quantità infinita di memoria.


199
2018-04-09 12:25



Oltre alle altre risposte corrette, potresti prendere in considerazione la possibilità di ridimensionare i valori per evitare problemi con l'aritmetica in virgola mobile.

Per esempio:

var result = 1.0 + 2.0;     // result === 3.0 returns true

... invece di:

var result = 0.1 + 0.2;     // result === 0.3 returns false

L'espressione 0.1 + 0.2 === 0.3 ritorna false in JavaScript, ma per fortuna l'aritmetica dei numeri interi in virgola mobile è esatta, quindi gli errori di rappresentazione decimale possono essere evitati mediante ridimensionamento.

Come esempio pratico, per evitare problemi in virgola mobile in cui la precisione è fondamentale, è consigliabile1 gestire il denaro come un intero che rappresenta il numero di centesimi: 2550 centesimi invece di 25.50 dollari.


1 Douglas Crockford: JavaScript: Le buone parti: Appendice A - Parti terribili (pagina 105).


98
2018-02-23 17:15



La mia risposta è piuttosto lunga, quindi l'ho divisa in tre sezioni. Poiché la domanda riguarda la matematica in virgola mobile, ho messo l'accento su ciò che la macchina effettivamente fa. Ho anche reso specifico il raddoppio (64 bit) di precisione, ma l'argomento si applica ugualmente a qualsiasi aritmetica in virgola mobile.

Preambolo

Un Formato a virgola mobile binario a precisione doppia IEEE 754 (binario64) numero rappresenta un numero del modulo

valore = (-1) ^ s * (1.m51m50... m2m1m0)2 * 2e-1023

in 64 bit:

  • Il primo bit è il segno di bit: 1 se il numero è negativo, 0 altrimenti1.
  • I prossimi 11 bit sono i esponente, che è compensare da 1023. In altre parole, dopo aver letto i bit dell'esponente da un numero doppiato, 1023 deve essere sottratta avere la potenza di due.
  • I restanti 52 bit sono i significando (o mantissa). Nella mantissa, un 'implicito' 1. è sempre2 omesso poiché il bit più significativo di qualsiasi valore binario è 1.

1 - IEEE 754 consente il concetto di a firmato zero - +0 e -0 sono trattati in modo diverso: 1 / (+0) è infinito positivo; 1 / (-0) è infinito negativo. Per i valori zero, i bit mantissa ed esponente sono tutti zero. Nota: i valori zero (+0 e -0) non sono esplicitamente classificati come denormali2.

2 - Questo non è il caso per numeri denormali, che hanno un esponente di offset pari a zero (e un implicito 0.). L'intervallo di numeri di doppia precisione denormali è dmin ≤ | x | ≤ dmax, dove dmin (il più piccolo numero rappresentabile diverso da zero) è 2-1023 - 51 (≈ 4,94 * 10-324) e dmax (il più grande numero denormale, per il quale la mantissa consiste interamente di 1s) è 2-1023 + 1 - 2-1023 - 51 (≈ 2.225 * 10-308).


Trasformare un numero doppio di precisione in binario

Esistono molti convertitori online per convertire un numero in virgola mobile a doppia precisione in binario (ad es binaryconvert.com), ma ecco alcuni esempi di codice C # per ottenere la rappresentazione IEEE 754 per un numero a precisione doppia (separo le tre parti con due punti (:):

public static string BinaryRepresentation(double value)
{
    long valueInLongType = BitConverter.DoubleToInt64Bits(value);
    string bits = Convert.ToString(valueInLongType, 2);
    string leadingZeros = new string('0', 64 - bits.Length);
    string binaryRepresentation = leadingZeros + bits;

    string sign = binaryRepresentation[0].ToString();
    string exponent = binaryRepresentation.Substring(1, 11);
    string mantissa = binaryRepresentation.Substring(12);

    return string.Format("{0}:{1}:{2}", sign, exponent, mantissa);
}

Arrivare al punto: la domanda originale

(Vai alla fine per la versione TL; DR)

Cato Johnston (il richiedente domanda) ha chiesto perché 0.1 + 0.2! = 0.3.

Scritto in binario (con i due punti che separano le tre parti), le rappresentazioni IEEE 754 dei valori sono:

0.1 => 0:01111111011:1001100110011001100110011001100110011001100110011010
0.2 => 0:01111111100:1001100110011001100110011001100110011001100110011010

Si noti che la mantissa è composta da cifre ricorrenti di 0011. Questo è chiave a perché c'è qualche errore nei calcoli - 0.1, 0.2 e 0.3 non possono essere rappresentati in binario precisamente in un finito il numero di bit binari più di 1/9, 1/3 o 1/7 può essere rappresentato con precisione in cifre decimali.

Conversione degli esponenti in decimale, rimozione dell'offset e riaggiustamento implicito 1 (tra parentesi quadre), 0.1 e 0.2 sono:

0.1 = 2^-4 * [1].1001100110011001100110011001100110011001100110011010
0.2 = 2^-3 * [1].1001100110011001100110011001100110011001100110011010

Per aggiungere due numeri, l'esponente deve essere lo stesso, cioè:

0.1 = 2^-3 *  0.1100110011001100110011001100110011001100110011001101(0)
0.2 = 2^-3 *  1.1001100110011001100110011001100110011001100110011010
sum = 2^-3 * 10.0110011001100110011001100110011001100110011001100111

Poiché la somma non è della forma 2n * 1. {bbb} aumentiamo l'esponente di uno e spostiamo il decimale (binario) punto per ottenere:

sum = 2^-2 * 1.0011001100110011001100110011001100110011001100110011(1)

Ora ci sono 53 bit nella mantissa (la 53a è racchiusa tra parentesi quadre nella riga sopra). Il predefinito modalità di arrotondamento per IEEE 754 è 'Arrotonda a più vicina'- cioè se un numero X cade tra due valori un e B, il valore in cui il bit meno significativo è zero viene scelto.

a = 2^-2 * 1.0011001100110011001100110011001100110011001100110011
x = 2^-2 * 1.0011001100110011001100110011001100110011001100110011(1)
b = 2^-2 * 1.0011001100110011001100110011001100110011001100110100

Nota che un e B differire solo nell'ultimo bit; ...0011 + 1 = ...0100. In questo caso, il valore con il bit meno significativo di zero è B, quindi la somma è:

sum = 2^-2 * 1.0011001100110011001100110011001100110011001100110100

TL; DR

scrittura 0.1 + 0.2 in una rappresentazione binaria IEEE 754 (con i due punti che separano le tre parti) e confrontandola con 0.3, questo è (ho messo i bit distinti tra parentesi quadre):

0.1 + 0.2 => 0:01111111101:0011001100110011001100110011001100110011001100110[100]
0.3       => 0:01111111101:0011001100110011001100110011001100110011001100110[011]

Convertito di nuovo in decimale, questi valori sono:

0.1 + 0.2 => 0.300000000000000044408920985006...
0.3       => 0.299999999999999988897769753748...

La differenza è esattamente 2-54, che è ~ 5.5511151231258 × 10-17 - insignificante (per molte applicazioni) rispetto ai valori originali.

Confrontare gli ultimi bit di un numero in virgola mobile è intrinsecamente pericoloso, come chiunque legga il famoso "Quello che ogni scienziato informatico dovrebbe sapere sull'aritmetica virgola mobile"(che copre tutte le parti principali di questa risposta) saprà.

La maggior parte dei calcolatori usa ulteriori cifre di guardia per aggirare questo problema, che è come 0.1 + 0.2 darebbe 0.3: gli ultimi bit sono arrotondati.


80
2018-03-16 05:27



I numeri in virgola mobile memorizzati nel computer sono costituiti da due parti, un intero e un esponente a cui la base viene portata e moltiplicata per la parte intera.

Se il computer funzionava nella base 10, 0.1 sarebbe 1 x 10⁻¹, 0.2 sarebbe 2 x 10⁻¹, e 0.3 sarebbe 3 x 10⁻¹. La matematica intera è facile e precisa, quindi aggiungendo 0.1 + 0.2 ovviamente comporterà 0.3.

I computer di solito non funzionano nella base 10, funzionano nella base 2. È comunque possibile ottenere risultati esatti per alcuni valori, ad esempio 0.5 è 1 x 2⁻¹ e 0.25 è 1 x 2⁻²e aggiungendoli risulta in 3 x 2⁻², o 0.75. Esattamente.

Il problema si presenta con numeri che possono essere rappresentati esattamente nella base 10, ma non nella base 2. Questi numeri devono essere arrotondati al loro equivalente più vicino. Supponendo il formato a virgola mobile IEEE a 64 bit molto comune, il numero più vicino a 0.1 è 3602879701896397 x 2⁻⁵⁵e il numero più vicino a 0.2 è 7205759403792794 x 2⁻⁵⁵; aggiungendo insieme risultati 10808639105689191 x 2⁻⁵⁵o un valore decimale esatto di 0.3000000000000000444089209850062616169452667236328125. I numeri in virgola mobile sono generalmente arrotondati per la visualizzazione.


48
2018-02-25 21:42