Por que alterar a ordem da soma retorna um resultado diferente?

Por que alterar a ordem da soma retorna um resultado diferente?

23.53 + 5.88 + 17.64 = 47.05

23.53 + 17.64 + 5.88 = 47.050000000000004

Ambos Java e JavaScript retornam os mesmos resultados.

Entendo que, devido à maneira como os números de ponto flutuante são representados em binário, alguns números racionais ( como 1/3 - 0,333333 ... ) não podem ser representados com precisão.

Por que simplesmente alterar a ordem dos elementos afeta o resultado?

Talvez essa pergunta seja estúpida, mas por que simplesmente mudar a ordem dos elementos afeta o resultado?

Ele mudará os pontos nos quais os valores são arredondados, com base em sua magnitude. Como exemplo do tipo de coisa que estamos vendo, vamos fingir que, em vez de ponto flutuante binário, estávamos usando um tipo de ponto flutuante decimal com 4 dígitos significativos, onde cada adição é executada com precisão "infinita" e arredondada para o número representável mais próximo. Aqui estão duas somas:

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)

Nem precisamos de números inteiros para que isso seja um 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

Isso demonstra possivelmente mais claramente que a parte importante é que temos um número limitado de dígitos significativos - não um número limitado de casas decimais . Se pudéssemos sempre manter o mesmo número de casas decimais, pelo menos com adição e subtração, ficaríamos bem (desde que os valores não ultrapassassem os limites). O problema é que, quando você chega a números maiores, informações menores são perdidas - o 10001 sendo arredondado para 10000 nesse caso. (Este é um exemplo do problema que Eric Lippert observou em sua resposta .)

É importante observar que os valores na primeira linha do lado direito são os mesmos em todos os casos - portanto, embora seja importante entender que seus números decimais (23,53, 5,88, 17,64) não serão representados exatamente como doublevalores, isso é apenas um problema devido aos problemas mostrados acima.

Aqui está o que está acontecendo em binário. Como sabemos, alguns valores de ponto flutuante não podem ser representados exatamente em binário, mesmo que possam ser representados exatamente em decimal. Esses três números são apenas exemplos desse fato.

Com este programa, produzo as representações hexadecimais de cada número e os resultados de cada adição.

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

O printValueAndInHexmétodo é apenas um auxiliar de impressora hexadecimal.

A saída é a seguinte:

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

Os primeiros 4 números são x, y, z, e s's representações hexadecimais. Na representação de ponto flutuante IEEE, os bits 2 a 12 representam o expoente binário , ou seja, a escala do número. (O primeiro bit é o bit de sinal e os bits restantes da mantissa .) O expoente representado é realmente o número binário menos 1023.

Os expoentes para os 4 primeiros números são extraídos:

    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

Primeiro conjunto de adições

O segundo número ( y) é de menor magnitude. Ao adicionar esses dois números para obter x + y, os últimos 2 bits do segundo número ( 01) são deslocados para fora do intervalo e não aparecem no cálculo.

A segunda adição adiciona x + ye ze acrescenta dois números da mesma escala.

Segundo conjunto de adições

Aqui, x + zocorre primeiro. Eles têm a mesma escala, mas produzem um número mais alto:

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

A segunda adição adiciona x + ze y, e agora são eliminados 3 bits ypara adicionar os números ( 101). Aqui, deve haver um arredondamento para cima, porque o resultado é o próximo número de ponto flutuante acima: 4047866666666666para o primeiro conjunto de adições vs. 4047866666666667para o segundo conjunto de adições. Esse erro é significativo o suficiente para aparecer na impressão do total.

Em conclusão, tenha cuidado ao executar operações matemáticas nos números IEEE. Algumas representações são inexatas e se tornam ainda mais inexatas quando as escalas são diferentes. Adicione e subtraia números de escala semelhante, se puder.

A resposta de Jon está obviamente correta. No seu caso, o erro não é maior que o erro que você acumularia ao executar qualquer operação simples de ponto flutuante. Você tem um cenário em que, em um caso, obtém um erro zero e em outro, um pequeno erro; esse não é realmente um cenário tão interessante. Uma boa pergunta é: existem cenários em que a alteração da ordem dos cálculos passa de um pequeno erro para um erro (relativamente) enorme? A resposta é inequivocamente sim.

Considere, por exemplo:

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, na aritmética exata, eles seriam os mesmos. É divertido tentar encontrar valores para a, b, c, d, e, f, g, h, de tal forma que os valores de x1 e x2 e x3 sejam diferentes em grande quantidade. Veja se você pode fazê-lo!

Na verdade, isso abrange muito mais do que apenas Java e Javascript, e provavelmente afetaria qualquer linguagem de programação usando flutuadores ou duplos.

Na memória, os pontos flutuantes usam um formato especial ao longo das linhas da IEEE 754 (o conversor fornece uma explicação muito melhor do que eu).

De qualquer forma, aqui está o conversor de flutuação.

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

A coisa sobre a ordem das operações é a "finura" da operação.

Sua primeira linha produz 29,41 dos dois primeiros valores, o que nos dá 2 ^ 4 como expoente.

Sua segunda linha produz 41,17, o que nos dá 2 ^ 5 como expoente.

Estamos perdendo um número significativo ao aumentar o expoente, o que provavelmente mudará o resultado.

Tente marcar o último bit na extrema direita para 41.17 e você pode ver que algo tão "insignificante" quanto 1/2 ^ 23 do expoente seria suficiente para causar essa diferença de ponto flutuante.

Edit: Para aqueles de vocês que se lembram de números significativos, isso se enquadra nessa categoria. 10 ^ 4 + 4999 com um número significativo de 1 será 10 ^ 4. Nesse caso, o número significativo é muito menor, mas podemos ver os resultados com o .00000000004 anexado a ele.

Os números de ponto flutuante são representados usando o formato IEEE 754, que fornece um tamanho específico de bits para a mantissa (significando). Infelizmente, isso fornece um número específico de 'blocos de construção fracionários' para brincar, e certos valores fracionários não podem ser representados com precisão.

O que está acontecendo no seu caso é que, no segundo caso, a adição provavelmente está ocorrendo algum problema de precisão devido à ordem em que as adições são avaliadas. Não calculei os valores, mas pode ser, por exemplo, que 23,53 + 17,64 não podem ser representados com precisão, enquanto 23,53 + 5,88 podem.

Infelizmente, é um problema conhecido com o qual você apenas precisa lidar.

Eu acredito que tem a ver com a ordem da evaulação. Enquanto a soma é naturalmente a mesma em um mundo de matemática, no mundo binário em vez de A + B + C = D, é

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

Portanto, existe uma etapa secundária em que os números de ponto flutuante podem sair.

Quando você altera a ordem,

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