Quando si usano i doppi, perché non è (x/(y * z)) lo stesso di (x/y/z)?

Question

Questo è in parte accademico, in quanto per i miei scopi ho solo bisogno arrotondato a due cifre decimali; ma sono desideroso di sapere cosa sta succedendo per produrre due risultati leggermente diversi.

Questa è la prova che ho scritto per limitare al semplice implementazione:

@Test 
public void shouldEqual() { 
    double expected = 450.00d/(7d * 60); // 1.0714285714285714 
    double actual = 450.00d/7d/60;  // 1.0714285714285716 

    assertThat(actual).isEqualTo(expected); 
} 

ma non riesce con questa uscita:

org.junit.ComparisonFailure: 
Expected :1.0714285714285714 
Actual :1.0714285714285716 

Qualcuno può spiegare in dettaglio cosa sta succedendo sotto il cappuccio per determinare il valore a 1.000000000000000 X è diverso?

Alcuni dei punti che sto cercando in una risposta sono: Dove viene persa la precisione? Quale metodo è preferito e perché? Quale è effettivamente corretto? (Nella pura matematica, entrambi non possono essere corretti. Forse entrambi hanno torto?) Esiste una soluzione o un metodo migliore per queste operazioni aritmetiche?

Answer 1

Vedo un sacco di domande che spiegano come risolvere questo problema, ma non quello che spiega realmente cosa sta succedendo, a parte "l'errore di arrotondamento a virgola mobile è negativo, m'kay?" Quindi lasciami fare un tentativo. Permettetemi innanzitutto di sottolineare che il numero in questa risposta non è specifico di Java. L'errore di arrotondamento è un problema inerente a qualsiasi rappresentazione di numeri a precisione fissa, quindi ottieni gli stessi problemi, ad esempio, in C.

errore di arrotondamento in un numero decimale tipo di dati

Come un esempio semplificato, immaginiamo di avere una sorta di computer che utilizza nativamente un unsigned decimale tipo di dati, chiamiamolo float6d. La lunghezza del tipo di dati è di 6 cifre: 4 dedicate alla mantissa e 2 dedicate all'esponente. Ad esempio, il numero 3,142 può essere espresso come

3.142 x 10^0 

che sarebbero memorizzate in 6 cifre come

503142 

Le prime due cifre sono l'esponente più 50, e gli ultimi quattro sono mantissa. Questo tipo di dati può rappresentare qualsiasi numero da 0.001 x 10^-50 a 9.999 x 10^+49.

In realtà, non è vero. Non è possibile memorizzare qualsiasi numero. Cosa succede se si desidera rappresentare 3.141592? O 3.1412034? O 3.141488906? Difficile, il tipo di dati non può memorizzare più di quattro cifre di precisione, quindi il compilatore deve arrotondare qualsiasi cosa con più cifre per adattarsi ai vincoli del tipo di dati. Se si scrive

float6d x = 3.141592; 
float6d y = 3.1412034; 
float6d z = 3.141488906; 

il compilatore converte ciascuno di questi tre valori per la stessa rappresentazione interna, 3.142 x 10^0 (che, ricordiamo, viene memorizzato come 503142), in modo che x == y == z terrà vero.

Il punto è che esiste un'intera gamma di numeri reali che si associano tutti alla stessa sequenza di cifre sottostante (o bit, in un computer reale). In particolare, qualsiasi x che soddisfa (supponendo arrotondamento semi-pari) viene convertito nella rappresentazione 503142 per l'archiviazione in memoria.

Questo arrotondamento avviene ogni volta il programma memorizza un valore a virgola mobile in memoria. La prima volta che succede è quando si scrive una costante nel codice sorgente, come ho fatto sopra con x, e z. Succede di nuovo ogni volta che si esegue un'operazione aritmetica che aumenta il numero di cifre di precisione oltre a quello che il tipo di dati può rappresentare. Uno di questi effetti è chiamato roundoff error. Ci sono alcuni modi diversi questo può accadere:

• Addizione e sottrazione: se uno dei valori che stai aggiungendo ha un esponente di diverso dagli altri, sarà vento con cifre supplementari di precisione, e se ce ne sono abbastanza, quelli meno significativi dovranno essere abbandonati. Ad esempio, 2.718 e 121.0 sono entrambi valori che possono essere rappresentati esattamente nel tipo di dati float6d. Ma se si tenta di aggiungere insieme:

  1.210  x 10^2 
  + 0.02718 x 10^2 
  ------------------- 
      1.23718 x 10^2 
  

  che viene arrotondato al 1.237 x 10^2, o 123,7, lasciando cadere due cifre di precisione.

• Moltiplicazione: il numero di cifre nel risultato è approssimativamente la somma del numero di cifre nei due operandi. Ciò produrrà un certo numero di errore roundoff, se i tuoi operandi hanno già molte cifre significative. Ad esempio, 121 x 2.718 ti dà

  1.210  x 10^2 
  x 0.02718 x 10^2 
  ------------------- 
      3.28878 x 10^2 
  

  che viene arrotondato a 3.289 x 10^2, o 328,9, lasciando cadere di nuovo due cifre di precisione.

  Tuttavia, è utile tenere presente che, se gli operandi sono numeri "carini", senza molte cifre significative, il formato a virgola mobile può probabilmente rappresentare esattamente il risultato, quindi non è necessario occuparsi di arrotondamento errore. Ad esempio, 2,3 x 140 dà

  1.40  x 10^2 
  x 0.23  x 10^2 
  ------------------- 
      3.22  x 10^2 
  

  che non ha problemi di arrotondamento.

• Divisione: è qui che le cose si complicano. La divisione sarà più o meno sempre causando una certa quantità di errore di arrotondamento a meno che il numero che si sta dividendo sia una potenza della base (nel qual caso la divisione è solo uno spostamento di cifre, o uno spostamento di bit in binario). Come esempio, prendere due numeri molto semplici, 3 e 7, dividerli, e si ottiene

  3.    x 10^0 
  /7.    x 10^0 
  ---------------------------- 
      0.428571428571... x 10^0 
  

  Il valore più vicino a questo numero che può essere rappresentato come un float6d è 4.286 x 10^-1 o 0,4286, che distintamente differisce dalla il risultato esatto.

Come vedremo nella prossima sezione, l'errore introdotto dall'arrotondamento cresce con ogni operazione eseguita. Dunque se stai lavorando con numeri "carini", come nel tuo esempio, generalmente è meglio fare le operazioni di divisione il più tardi possibile perché quelle sono le operazioni che con maggiore probabilità introdurranno errori di arrotondamento nel tuo programma dove prima non esisteva nessuno.

Analisi di errore di arrotondamento

In generale, se non si può assumere i numeri sono "belle", errore di arrotondamento può essere positivo o negativo, ed è molto difficile prevedere quale direzione andrà solo in base sull'operazione. Dipende dai valori specifici coinvolti. Guardate questo grafico della errore di arrotondamento per 2.718 z in funzione della z (ancora utilizzando il tipo di dati float6d):

In pratica, quando si lavora con i valori che utilizzano la precisione completa del vostro tipo di dati, è spesso più semplice trattare l'errore di arrotondamento come un errore casuale. Osservando la trama, si potrebbe essere in grado di indovinare che la grandezza dell'errore dipende dall'ordine di grandezza del risultato dell'operazione. In questo caso particolare, quando z è dell'ordine 10 ^-1, 2.718 z è anche dell'ordine di 10 ^-1, quindi sarà un numero del modulo 0.XXXX. L'errore di arrotondamento massimo è quindi la metà dell'ultima cifra di precisione; in questo caso, per "l'ultima cifra di precisione" intendo 0,0001, quindi l'errore di arrotondamento varia tra -0,00005 e +0,00005. Nel punto in cui 2.718 z salta al successivo ordine di grandezza, che è 1/2.718 = 0,3679, puoi vedere che l'errore di arrotondamento salta anche di un ordine di grandezza.

È possibile utilizzare il noto techniques of error analysis per analizzare come un errore casuale (o imprevedibile) di una certa entità influisce sul risultato.In particolare, per la moltiplicazione o la divisione, l'errore relativo alla "media" del risultato può essere approssimato aggiungendo l'errore relativo in ciascuno degli operandi in quadratura - ovvero, quadrato, aggiungerli e prendere la radice quadrata. Con il nostro tipo di dati float6d, l'errore relativo varia tra 0,0005 (per un valore come 0,101) e 0,00005 (per un valore come 0,995).

Diamo 0,0001 come media massima per l'errore relativo a valori x e y. L'errore relativo x * y o x/y è data da

sqrt(0.0001^2 + 0.0001^2) = 0.0001414 

che è un fattore di sqrt(2) maggiore l'errore relativo a ciascuno dei singoli valori.

Quando si tratta di combinare operazioni, è possibile applicare questa formula più volte, una volta per ogni operazione in virgola mobile. Così, per esempio, per z/(x * y), l'errore relativo x * y è, in media, ,0001,414 mila (in questo esempio decimale) e quindi l'errore relativo z/(x * y) è

sqrt(0.0001^2 + 0.0001414^2) = 0.0001732 

noti che l'errore relativo medio cresce ad ogni operazione, in particolare come radice quadrata del numero di moltiplicazioni e divisioni che si fanno.

Analogamente, per z/x * y, l'errore relativo medio in z/x è ,0001,414 mila, e l'errore relativo z/x * y è

sqrt(0.0001414^2 + 0.0001^2) = 0.0001732 

Così, lo stesso, in questo caso. Ciò significa che per valori arbitrari, in media, le due espressioni introducono approssimativamente lo stesso errore. (In teoria, ciò che è. Ho visto queste operazioni si comportano in modo molto diverso, in pratica, ma questa è un'altra storia.)

dettagli scabrosi

Potreste essere curioso di sapere il calcolo specifica hai presentato nella questione , non solo una media. Per questa analisi, passiamo al mondo reale dell'aritmetica binaria. I numeri in virgola mobile nella maggior parte dei sistemi e delle lingue sono rappresentati utilizzando IEEE standard 754. Per i numeri a 64 bit, lo format specifica 52 bit dedicati alla mantissa, 11 all'esponente e uno al segno. In altre parole, quando scritti in base 2, un numero decimale è un valore del modulo

1.1100000000000000000000000000000000000000000000000000 x 2^00000000010 
         52 bits        11 bits 

Il principale 1 non espressamente memorizzato, e costituisce un po 53a. Inoltre, dovresti notare che gli 11 bit memorizzati per rappresentare l'esponente sono in realtà il vero esponente più il 1023. Ad esempio, questo particolare valore è 7, che è 1,75 x 2 . La mantissa è 1.75 in binario, o 1.11, e l'esponente è 1.023 + 2 = 1025 in binario, o 10000000001, in modo che il contenuto memorizzato nella memoria è

01000000000111100000000000000000000000000000000000000000000000000 
^  ^
exponent mantissa 

ma che non ha molta importanza.

Il vostro esempio coinvolge anche 450,

1.1100001000000000000000000000000000000000000000000000 x 2^00000001000 

e 60,

1.1110000000000000000000000000000000000000000000000000 x 2^00000000101 

Si può giocare con questi valori utilizzando this converter o uno dei molti altri su Internet.

Quando si calcola la prima espressione, 450/(7*60), il primo processore fa la moltiplicazione, ottenendo 420, o

1.1010010000000000000000000000000000000000000000000000 x 2^00000001000 

Poi divide 450 da 420. Questo produce 15/14, che è

1.0001001001001001001001001001001001001001001001001001001001001001001001... 

in binario. Ora, the Java language specification dice che

I risultati inesatti devono essere arrotondati al valore rappresentabile più vicino al risultato infinitamente preciso; se i due valori rappresentativi più vicini sono ugualmente vicini, viene scelto quello con il suo bit zero meno significativo. Questa è la modalità di arrotondamento predefinita dello standard IEEE 754, nota come round to nearest.

e il valore rappresentabile più vicina a 15/14 in formato a 64 bit IEEE 754 è

1.0001001001001001001001001001001001001001001001001001 x 2^00000000000 

ossia circa 1.0714285714285714 in decimale. (Più precisamente, questo è il valore decimale meno preciso che specifica in modo univoco questa particolare rappresentazione binaria.)

D'altra parte, se si calcola prima 450/7, il risultato è 64.2857142857 ... o in binario,

1000000.01001001001001001001001001001001001001001001001001001001001001001... 

per i quali il valore rappresentabile più vicino è

1.0000000100100100100100100100100100100100100100100101 x 2^00000000110 

che è 64,28571428571429180465 ... si noti il ​​cambiamento l'ultima cifra della mantissa binario (rispetto al valore esatto) a causa di errore di arrotondamento. Dividere questo per 60 ti dà

1.000100100100100100100100100100100100100100100100100110011001100110011... 

Guarda alla fine: il modello è diverso! È 0011 che si ripete, invece di 001 come nell'altro caso. Il valore rappresentabile più vicino è

1.0001001001001001001001001001001001001001001001001010 x 2^00000000000 

che differisce dalle altre ordine delle operazioni negli ultimi due bit: sono 10 anziché 01. L'equivalente decimale è 1,0714285714285716.

L'arrotondamento specifica che causa questa differenza dovrebbe essere chiaro se si guardano le esatte valori binari:

1.0001001001001001001001001001001001001001001001001001001001001001001001... 
1.0001001001001001001001001001001001001001001001001001100110011001100110... 
                ^last bit of mantissa 

Funziona in questo caso che il primo risultato, numericamente 15/14, sembra essere il rappresentazione più accurata del valore esatto. Questo è un esempio di come lasciare la divisione fino alla fine è un vantaggio per te.Ma ancora una volta, questa regola vale finché i valori con cui stai lavorando non usano la precisione completa del tipo di dati. Quando inizi a lavorare con valori inesatti (arrotondati), non ti proteggi più da ulteriori errori di arrotondamento eseguendo prima le moltiplicazioni.

Answer 2

Certamente l'ordine delle operazioni mescolato con il fatto che doppie non sono precise:

450.00d/(7d * 60) --> a = 7d * 60 --> result = 450.00d/a 

vs

450.00d/7d/60 --> a = 450.00d /7d --> result = a/60 

Answer 3

Questo perché doppia divisione spesso portano ad una perdita di precisione. Detta perdita può variare in base all'ordine delle divisioni.

Quando dividi per 7d, hai già perso una certa precisione con il risultato effettivo. Quindi solo tu dividi un risultato errato per 60.

Quando si divide per 7d * 60, è necessario utilizzare la divisione solo una volta, perdendo quindi la precisione una sola volta.

Si noti che a volte può verificarsi anche una doppia moltiplicazione, ma è molto meno comune.

Answer 4

Ha a che fare con l'implementazione del tipo double e il fatto che i tipi a virgola mobile non garantiscono la stessa precisione di altri tipi più semplici. Sebbene la risposta seguente sia più specificatamente relativa alle somme, risponde anche alla tua domanda spiegando come non vi è alcuna garanzia di precisione infinita nelle operazioni matematiche a virgola mobile: Why does changing the sum order returns a different result?. In sostanza, non si dovrebbe mai tentare di determinare l'uguaglianza dei valori in virgola mobile senza specificare un margine di errore accettabile. La libreria Guava di Google include DoubleMath.fuzzyEquals(double, double, double) per determinare l'uguaglianza di due valori double entro una certa precisione. Se si desidera leggere le specifiche dell'eguaglianza in virgola mobile this site is quite useful; lo stesso sito also explains floating-point rounding errors. In sommatoria: i valori previsti e effettivi del calcolo differiscono a causa dell'arrotondamento che differisce tra i calcoli dovuti all'ordine delle operazioni.

Answer 5

Semplifichiamo un po 'le cose. Quello che vuoi sapere è perché 450d/420 e 450d/7/60 (in particolare) danno risultati diversi.

Vediamo come viene eseguita la divisione nel formato in virgola mobile a precisione doppia IEE. Senza approfondire i dettagli dell'implementazione, è fondamentalmente lo XOR, ovvero il bit del segno, sottraendo l'esponente del divisore dall'esponente del dividendo, dividendo le mantisse e normalizzando il risultato.

In primo luogo, dobbiamo rappresentare i nostri numeri nel formato corretto per double: prima divide

450 is 0 10000000111 1100001000000000000000000000000000000000000000000000 

420 is 0 10000000111 1010010000000000000000000000000000000000000000000000 

7  is 0 10000000001 1100000000000000000000000000000000000000000000000000 

60  is 0 10000000100 1110000000000000000000000000000000000000000000000000 

Let 450 da 420

Prima viene il bit di segno, è 0 (0 xor 0 == 0).

Quindi arriva l'esponente. 10000000111b - 10000000111b + 1023 == 10000000111b - 10000000111b + 01111111111b == 01111111111b

Guardando bene, ora la mantissa:

1.1100001000000000000000000000000000000000000000000000/1.1010010000000000000000000000000000000000000000000000 == 1.1100001/1.101001. Ci sono un paio di modi diversi per farlo, ne parlerò un po 'dopo. Il risultato è 1.0(001) (è possibile verificarlo here).

Ora dovremmo normalizzare il risultato. Vediamo i valori di guardia, rotonde e sticky bit:

0001001001001001001001001001001001001001001001001001 0 0 1

di 0 Guardia po ', non facciamo alcun arrotondamento. Il risultato è, in binario:

0 01111111111 0001001001001001001001001001001001001001001001001001

che viene rappresentato come 1.0714285714285714 in decimale.

Oramai dividere 450 per 7 per analogia.

Segno po = 0

Esponente = 10000000111b - 10000000001b + 01111111111b == -01111111001b + 01111111111b + 01111111111b == 10000000101b

Mantissa = 1.1100001/1.11 == 1.00000(001)

Arrotondamento:

0000000100100100100100100100100100100100100100100100 1 0 0

Guardia bit è impostato, rotondo e bit sticky non lo sono. Stiamo arrotondando al più vicino (modalità predefinita per IEEE) e siamo bloccati tra i due valori possibili a cui potremmo arrotondare. Poiché lsb è 0, aggiungiamo 1.Questo ci dà la mantissa arrotondata:

0000000100100100100100100100100100100100100100100101

Il risultato è

0 10000000101 0000000100100100100100100100100100100100100100100101

che viene rappresentato come 64.28571428571429 in decimale.

Ora dovremo dividerlo per 60 ... Ma sai già che abbiamo perso un po 'di precisione. La divisione 450 per il numero 420 non ha richiesto alcun arrotondamento, ma qui, abbiamo già dovuto arrotondare il risultato almeno una volta. Ma, per l'amor di completezza, facciamo finire il lavoro:

Dividendo 64.28571428571429 da 60

bit di segno = 0

Esponente = 10000000101b - 10000000100b + 01111111111b == 01111111110b

Mantissa = 1.0000000100100100100100100100100100100100100100100101/1.111 == 0.10001001001001001001001001001001001001001001001001001100110011

rotonda e lo spostamento :

0.1000100100100100100100100100100100100100100100100100 1 1 0 0 

1.0001001001001001001001001001001001001001001001001001 1 0 0 

Arrotondamento come nel caso precedente, otteniamo la mantissa: 0001001001001001001001001001001001001001001001001010.

Come abbiamo spostato da 1, aggiungiamo che per l'esponente, ottenendo

Esponente = 01111111111b

Quindi, il risultato è:

0 01111111111 0001001001001001001001001001001001001001001001001010

che viene rappresentato come 1.0714285714285716 in decimale.

Tl; dr:

La prima divisione ci ha dato:

0 01111111111 0001001001001001001001001001001001001001001001001001

E l'ultima divisione ci ha dato:

0 01111111111 0001001001001001001001001001001001001001001001001010

La differenza è nel ultimi 2 bit solo, ma avremmo potuto perdere di più - dopo tutto, per ottenere il secondo risultato, abbiamo dovuto arrotondare due volte anziché nessuna!

Ora, sulla divisione mantissa. La divisione in virgola mobile è implementata in due modi principali.

Le modalità richieste dalla divisione lunga IEEE (here sono alcuni buoni esempi: è fondamentalmente la divisione lunga normale, ma con binario anziché decimale) ed è piuttosto lenta. Questo è ciò che ha fatto il tuo computer.

C'è anche un'opzione più veloce ma meno precisa, moltiplicazione per inverso. Prima viene trovato un reciproco del divisore, quindi viene eseguita la moltiplicazione.