¿Por qué cambiar el orden de la suma devuelve un resultado diferente?

¿Por qué cambiar el orden de la suma devuelve un resultado diferente?

23.53 + 5.88 + 17.64 = 47.05

23.53 + 17.64 + 5.88 = 47.050000000000004

Tanto Java como JavaScript devuelven los mismos resultados.

Entiendo que, debido a la forma en que los números de coma flotante se representan en binario, algunos números racionales ( como 1/3 - 0.333333 ... ) no se pueden representar con precisión.

¿Por qué simplemente cambiar el orden de los elementos afecta el resultado?

Tal vez esta pregunta es estúpida, pero ¿por qué simplemente cambiar el orden de los elementos afecta el resultado?

Cambiará los puntos en los que se redondean los valores, en función de su magnitud. Como ejemplo del tipo de cosas que estamos viendo, imaginemos que en lugar de coma flotante binaria, estábamos usando un tipo de coma flotante decimal con 4 dígitos significativos, donde cada suma se realiza con precisión "infinita" y luego se redondea a El número representable más cercano. Aquí hay dos sumas:

1/3 + 2/3 + 2/3 = (0.3333 + 0.6667) + 0.6667
                = 1.000 + 0.6667 (no rounding needed!)
                = 1.667 (where 1.6667 is rounded to 1.667)

2/3 + 2/3 + 1/3 = (0.6667 + 0.6667) + 0.3333
                = 1.333 + 0.3333 (where 1.3334 is rounded to 1.333)
                = 1.666 (where 1.6663 is rounded to 1.666)

Ni siquiera necesitamos números enteros para que esto sea un problema:

10000 + 1 - 10000 = (10000 + 1) - 10000
                  = 10000 - 10000 (where 10001 is rounded to 10000)
                  = 0

10000 - 10000 + 1 = (10000 - 10000) + 1
                  = 0 + 1
                  = 1

Esto demuestra posiblemente más claramente que la parte importante es que tenemos un número limitado de dígitos significativos , no un número limitado de decimales . Si siempre pudiéramos mantener el mismo número de lugares decimales, entonces con suma y resta al menos, estaríamos bien (siempre que los valores no se desbordaran). El problema es que cuando se llega a números más grandes, se pierde información más pequeña: el 10001 se redondea a 10000 en este caso. (Este es un ejemplo del problema que Eric Lippert notó en su respuesta ).

Es importante tener en cuenta que los valores en la primera línea del lado derecho son los mismos en todos los casos, por lo que, aunque es importante comprender que sus números decimales (23.53, 5.88, 17.64) no se representarán exactamente como doublevalores, eso es solo un problema debido a los problemas que se muestran arriba.

Esto es lo que está sucediendo en binario. Como sabemos, algunos valores de punto flotante no se pueden representar exactamente en binario, incluso si se pueden representar exactamente en decimal. Estos 3 números son solo ejemplos de ese hecho.

Con este programa, saco las representaciones hexadecimales de cada número y los resultados de cada suma.

public class Main{
   public static void main(String args[]) {
      double x = 23.53;   // Inexact representation
      double y = 5.88;    // Inexact representation
      double z = 17.64;   // Inexact representation
      double s = 47.05;   // What math tells us the sum should be; still inexact

      printValueAndInHex(x);
      printValueAndInHex(y);
      printValueAndInHex(z);
      printValueAndInHex(s);

      System.out.println("--------");

      double t1 = x + y;
      printValueAndInHex(t1);
      t1 = t1 + z;
      printValueAndInHex(t1);

      System.out.println("--------");

      double t2 = x + z;
      printValueAndInHex(t2);
      t2 = t2 + y;
      printValueAndInHex(t2);
   }

   private static void printValueAndInHex(double d)
   {
      System.out.println(Long.toHexString(Double.doubleToLongBits(d)) + ": " + d);
   }
}

El printValueAndInHexmétodo es solo un ayudante de impresora hexadecimal.

El resultado es el siguiente:

403787ae147ae148: 23.53
4017851eb851eb85: 5.88
4031a3d70a3d70a4: 17.64
4047866666666666: 47.05
--------
403d68f5c28f5c29: 29.41
4047866666666666: 47.05
--------
404495c28f5c28f6: 41.17
4047866666666667: 47.050000000000004

Los primeros 4 números son x, y, z, y s's representaciones hexadecimales. En la representación de coma flotante IEEE, los bits 2-12 representan el exponente binario , es decir, la escala del número. (El primer bit es el bit de signo y los bits restantes para la mantisa .) El exponente representado es en realidad el número binario menos 1023.

Se extraen los exponentes para los primeros 4 números:

    sign|exponent
403 => 0|100 0000 0011| => 1027 - 1023 = 4
401 => 0|100 0000 0001| => 1025 - 1023 = 2
403 => 0|100 0000 0011| => 1027 - 1023 = 4
404 => 0|100 0000 0100| => 1028 - 1023 = 5

Primer conjunto de adiciones

El segundo número ( y) es de menor magnitud. Al sumar estos dos números para obtener x + y, los últimos 2 bits del segundo número ( 01) se desplazan fuera del rango y no figuran en el cálculo.

La segunda suma agrega x + yy zagrega dos números de la misma escala.

Segundo conjunto de adiciones

Aquí, x + zocurre primero. Son de la misma escala, pero producen un número que es más alto en la escala:

404 => 0|100 0000 0100| => 1028 - 1023 = 5

La segunda suma agrega x + zy y, y ahora se eliminan 3 bits ypara agregar los números ( 101). Aquí, debe haber una ronda hacia arriba, porque el resultado es el siguiente número de coma flotante hacia arriba: 4047866666666666para el primer conjunto de adiciones vs.4047866666666667 para el segundo conjunto de adiciones. Ese error es lo suficientemente significativo como para mostrarse en la impresión del total.

En conclusión, tenga cuidado al realizar operaciones matemáticas en números IEEE. Algunas representaciones son inexactas, y se vuelven aún más inexactas cuando las escalas son diferentes. Suma y resta números de escala similar si puedes.

La respuesta de Jon es, por supuesto, correcta. En su caso, el error no es mayor que el error que acumularía al realizar cualquier operación simple de coma flotante. Tienes un escenario en el que en un caso obtienes cero errores y en otro obtienes un pequeño error; ese no es realmente un escenario tan interesante. Una buena pregunta es: ¿hay escenarios en los que cambiar el orden de los cálculos pasa de un pequeño error a un error (relativamente) enorme?La respuesta es inequívocamente sí.

Considere por ejemplo:

x1 = (a - b) + (c - d) + (e - f) + (g - h);

vs

x2 = (a + c + e + g) - (b + d + f + h);

vs

x3 = a - b + c - d + e - f + g - h;

Obviamente en aritmética exacta serían lo mismo. Es entretenido tratar de encontrar valores para a, b, c, d, e, f, g, h de manera que los valores de x1 y x2 y x3 difieran en gran cantidad. ¡Mira si puedes hacerlo!

En realidad, esto cubre mucho más que Java y Javascript, y probablemente afectaría cualquier lenguaje de programación que use flotantes o dobles.

En la memoria, los puntos flotantes utilizan un formato especial a lo largo de las líneas de IEEE 754 (el convertidor proporciona una explicación mucho mejor que yo).

De todos modos, aquí está el convertidor de flotador.

http://www.h-schmidt.net/FloatConverter/

Lo importante del orden de las operaciones es la "finura" de la operación.

Su primera línea produce 29.41 de los dos primeros valores, lo que nos da 2 ^ 4 como exponente.

Su segunda línea produce 41.17, lo que nos da 2 ^ 5 como exponente.

Estamos perdiendo una cifra significativa al aumentar el exponente, lo que probablemente cambie el resultado.

Intente marcar el último bit en el extremo derecho dentro y fuera de 41.17 y puede ver que algo tan "insignificante" como 1/2 ^ 23 del exponente sería suficiente para causar esta diferencia de coma flotante.

Editar: para aquellos de ustedes que recuerdan cifras significativas, esto caería dentro de esa categoría. 10 ^ 4 + 4999 con una cifra significativa de 1 será 10 ^ 4. En este caso, la cifra significativa es mucho menor, pero podemos ver los resultados con el .00000000004 adjunto.

Los números de coma flotante se representan utilizando el formato IEEE 754, que proporciona un tamaño específico de bits para la mantisa (significado). Desafortunadamente, esto le da un número específico de 'bloques de construcción fraccionales' para jugar, y ciertos valores fraccionarios no se pueden representar con precisión.

Lo que está sucediendo en su caso es que en el segundo caso, la adición probablemente se encuentre con algún problema de precisión debido al orden en que se evalúan las adiciones. No he calculado los valores, pero podría ser, por ejemplo, que 23.53 + 17.64 no se puede representar con precisión, mientras que 23.53 + 5.88 sí.

Desafortunadamente, es un problema conocido con el que solo tiene que lidiar.

Creo que tiene que ver con el orden de evacuación. Si bien la suma es naturalmente la misma en un mundo matemático, en el mundo binario en lugar de A + B + C = D, es

A + B = E
E + C = D(1)

Entonces está ese paso secundario donde los números de coma flotante pueden bajar.

Cuando cambias el orden,

A + C = F
F + B = D(2)