Perché l'ordine influisce l'arrotondamento quando si aggiungono più doppie in C #

Question

Si consideri il seguente codice C #:

double result1 = 1.0 + 1.1 + 1.2;
double result2 = 1.2 + 1.0 + 1.1;

if (result1 == result2)
{
    ...
}

result1 dovrebbe sempre uguale result2 giusto? La cosa è, non è così. result1 è 3.3 e risultato2 è 3,3000000000000003. L'unica differenza è l'ordine delle costanti.

So che raddoppia sono implementati in modo tale che si possono verificare problemi di arrotondamento. Sono consapevole che posso usare decimali invece se ho bisogno di una precisione assoluta. O che posso usare Math.round () nel mio if. Sono solo un nerd che vuole capire ciò che il compilatore C # sta facendo. Qualcuno può dirmi?

Modifica

Grazie a tutti coloro che finora hanno suggerito la lettura su aritmetica in virgola mobile e / o parlato l'imprecisione intrinseca di come la CPU gestisce doppie. Ma sento la spinta principale della mia domanda è ancora senza risposta. Qual è la mia colpa per non fraseggio correttamente. Mettiamola in questo modo:

Abbattere il codice di cui sopra, mi sarei aspettato le seguenti operazioni da accadendo:

double r1 = 1.1 + 1.2;
double r2 = 1.0 + r1
double r3 = 1.0 + 1.1
double r4 = 1.2 + r3

Supponiamo che ciascuna delle aggiunte sopra aveva un errore di arrotondamento (e1..e4 numerato). Così r1 contiene arrotondamento errore e1, R2 include errori di arrotondamento E1 + E2, E3 r3 contiene e r4 contiene e3 + e4.

Ora, io non so come esattamente come gli errori di arrotondamento accadere, ma mi sarei aspettato E1 + E2 pari e3 + e4. Chiaramente non è così, ma che sembra in qualche modo sbagliato per me. Un'altra cosa è che quando faccio funzionare il codice di cui sopra, non ho ricevuto alcun errori di arrotondamento. Questo è quello che mi fa pensare che sia il compilatore C # che sta facendo qualcosa di strano, piuttosto che la CPU.

So che sto chiedendo molto e forse la risposta migliore chiunque può dare è quello di andare a fare un dottorato di ricerca nel design della CPU, ma ho solo pensato che avrei chiesto.

Modifica 2

Guardando il IL da mio campione codice originale, è chiaro che è il compilatore non la CPU che sta facendo questo:

.method private hidebysig static void Main(string[] args) cil managed
{
.entrypoint
    .maxstack 1
    .locals init (
        [0] float64 result1,
        [1] float64 result2)
    L_0000: nop 
    L_0001: ldc.r8 3.3
    L_000a: stloc.0 
    L_000b: ldc.r8 3.3000000000000003
    L_0014: stloc.1 
    L_0015: ret 
}

Il compilatore sta aggiungendo i numeri per me!

Answer 1

  

Mi sarei aspettato E1 + E2 pari e3 + e4.

Non è del tutto dissimile attesa

 floor( 5/3 ) + floor( 2/3 + 1 )

alla parità

 floor( 5/3 + 2/3 ) + floor( 1 )

tranne che si sta moltiplicando per 2 ^ 53 prima di prendere la parola.

Utilizzando virgola mobile a 12 bit di precisione e troncamento con i propri valori:

1.0            =  1.00000000000
1.1            =  1.00011001100
1.2            =  1.00110011001

1.0 + 1.1      = 10.00011001100 // extended during sum
r1 = 1.0 + 1.1 = 10.0001100110  // truncated to 12 bit
r1  + 1.2      = 11.01001100101 // extended during sum
r2 = r1  + 1.2 = 11.0100110010  // truncated to 12 bit

1.1 + 1.2      = 10.01001100110 // extended during sum
r3 = 1.1 + 1.2 = 10.0100110011  // truncated to 12 bit
r3 + 1.0       = 11.01001100110 // extended during sum
r4 = r3  + 1.0 = 11.0100110011  // truncated to 12 bit

Quindi, cambiare l'ordine delle operazioni / troncamenti causa l'errore di cambiare, e r4! = R2. Se si aggiungono 1.1 e 1.2 in questo sistema, l'ultimo bit porta, quindi in non si perde il troncamento. Se si aggiungono 1,0 a 1,1, l'ultimo pezzo di 1.1 è persa e quindi il risultato non è lo stesso.

In un ordinamento, l'arrotondamento (per troncamento) rimuove un 1 finale.

Nell'altra ordinamento, l'arrotondamento rimuove un 0 finale entrambe le volte.

Uno non è uguale a zero; quindi gli errori non sono gli stessi.

Doppio hanno molti più bit di precisione, e C # probabilmente usa l'arrotondamento piuttosto che troncamento, ma spero che questo semplice modello mostra diversi errori possono accadere con diversi ordinamenti degli stessi valori.

La differenza tra FP e la matematica è che + è una scorciatoia per 'aggiungere poi round' piuttosto che aggiungere.

Answer 2

Il compilatore C # non sta facendo nulla. La CPU è.

Se avete una in un registro della CPU, e poi si aggiungono B, il risultato memorizzato in tale registro è A + B, approssimata per la precisione galleggiante utilizzato

Se poi si aggiungono C, l'errore aggiunge. Questa aggiunta errore non è un'operazione transitivo, così l'ultima differenza.

Answer 3

la carta classica (Ciò che ogni informatico dovrebbe conoscere floating-point aritmetica) sull'argomento. Questo genere di cose è ciò che accade con aritmetica in virgola mobile. Ci vuole uno scienziato informatico per dirvi che 1/3 + 1/3 + 1/3 is'nt uguale a 1 ...

Answer 4

Ordine di operazioni in virgola mobile è importante. Non risponde direttamente alla tua domanda, ma si dovrebbe sempre essere attenti a confronto i numeri in virgola mobile. E 'usuale per includere una tolleranza:

double epsilon = 0.0000001;
if (abs(result1 - result2) <= epsilon)
{
    ...
}

Questo può essere di interesse: Ciò che ogni computer Scientist dovrebbe sapere floating punto aritmetica

Answer 5

  

result1 dovrebbe sempre uguale result2   giusto?

sbagliato . Questo è vero in matematica, ma non in in virgola mobile aritmetica .

È necessario leggere alcune Analisi Numerica Primer .

Answer 6

Perché gli errori non sono le stesse a seconda ordine può essere spiegato con un esempio diverso.

Diciamo che per i numeri inferiori a 10, è in grado di memorizzare tutti i numeri, in modo che possa immagazzinare 1, 2, 3, e così via fino al 10, ma dopo 10, può memorizzare solo ogni secondo numero, a causa alla perdita interna di precisione, in altre parole, si può memorizzare solo 10, 12, 14, ecc.

Ora, con questo esempio, vedrete perché il seguente produce risultati diversi:

1 + 1 + 1 + 10 = 12 (or 14, depending on rounding)
10 + 1 + 1 + 1 = 10

Il problema con i numeri in virgola mobile è che essi non possono essere rappresentati con precisione, e l'errore non va sempre allo stesso modo, per cui l'ordine si importa.

Per esempio, 3,00000000003 + 3,00000000003 potrebbe finire per essere 6,00000000005 (avviso non 6 alla fine), ma 3,00000000003 + 2,99999999997 potrebbe finire per essere 6,00000000001, e con questo:

step 1: 3.00000000003 + 3.00000000003 = 6.00000000005
step 2: 6.00000000005 + 2.99999999997 = 9.00000000002

ma, cambiare l'ordine:

step 1: 3.00000000003 + 2.99999999997 = 6.00000000001
step 2: 6.00000000001 + 3.00000000003 = 9.00000000004

Così importa.

Ora, naturalmente, si potrebbe essere fortunati, perché gli esempi sopra equilibrio a vicenda, in quanto il primo oscillerà da .xxx1 e l'altro dalla .xxx1, dandovi .xxx3 in entrambi, ma non c'è garanzia.

Answer 7

Si sono effettivamente non utilizza gli stessi valori, perché i risultati intermedi sono diversi:

double result1 = 2.1 + 1.2;
double result2 = 2.2 + 1.1;

A causa doppie non possono rappresentare valori decimali esattamente si ottengono risultati diversi.