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

294

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?

Marlon Bernardes
fonte
28
A soma dos números reais é associativa e comutativa. Pontos flutuantes não são números reais. Na verdade, você acabou de provar que suas operações não são comutativas. É muito fácil mostrar que eles também não são associativos (por exemplo (2.0^53 + 1) - 1 == 2.0^53 - 1 != 2^53 == 2^53 + (1 - 1)). Portanto, sim: tenha cuidado ao escolher a ordem das somas e outras operações. Algumas linguagens fornecem um built-in para executar somas de "alta precisão" (por exemplo, python's math.fsum), portanto, você pode considerar o uso dessas funções em vez do ingênuo algoritmo de soma.
Bakuriu 6/11
1
@RBerteig Isso pode ser determinado examinando a ordem das operações do idioma para expressões aritméticas e, a menos que a representação dos números de ponto flutuante na memória seja diferente, os resultados serão os mesmos se as regras de precedência do operador forem as mesmas. Outro ponto de observação: gostaria de saber quanto tempo os desenvolvedores que desenvolvem aplicativos bancários levaram para descobrir isso? Esses centavos extras de 0000000000004 realmente somam!
22813 Chris Cirefice
3
@ ChrisCirefice: se você tem 0,00000004 centavos , está fazendo errado. Você nunca deve usar um tipo de ponto flutuante binário para cálculos financeiros.
precisa saber é o seguinte
2
@DanielPryden Ah, infelizmente, foi uma piada ... apenas brincar com a idéia de que as pessoas que realmente precisam resolver esse tipo de problema tinham um dos trabalhos mais importantes que você conhece, detém o status monetário das pessoas e tudo mais . Eu estava sendo muito sarcástico ...
Chris Cirefice
6
Muito seco (e velhos, mas ainda relevante): O que cada cientista computador deve saber sobre Floating-Point Arithmetic
Brian

Respostas:

276

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.

Jon Skeet
fonte
10
May extend this later - out of time right now!esperando ansiosamente por ele @Jon
Prateek
3
quando digo que voltarei a uma resposta mais tarde, a comunidade é um pouco menos gentil comigo <digite algum tipo de emoticon alegre para mostrar que estou brincando e não um idiota> ... voltarei a isso mais tarde.
Grady Player
2
@ZongZhengLi: Embora seja certamente importante entender isso, não é a causa raiz neste caso. Você poderia escrever um exemplo semelhante com os valores que são representados exatamente em binário, e ver o mesmo efeito. O problema aqui é manter informações em grande escala e informações em pequena escala ao mesmo tempo.
perfil completo de Jon Skeet
1
@ Buksy: arredondado para 10000 - porque estamos lidando com um tipo de dados que pode armazenar apenas 4 dígitos significativos. (so x.xxx * 10 ^ n)
Jon Skeet
3
@eteus: Não, isso não causa um estouro - e você está usando os números errados. É 10001 sendo arredondado para 10000, e não 1001 sendo arredondado para 1000. Para tornar mais claro, 54321 seria arredondado para 54320 - porque isso possui apenas quatro dígitos significativos. Há uma grande diferença entre "quatro dígitos significativos" e "um valor máximo de 9999". Como eu disse antes, você está basicamente representando x.xxx * 10 ^ n, onde para 10000, x.xxx seria 1.000 e n seria 4. Isso é como doublee float, para números muito grandes, números representativos consecutivos são mais do que 1 separados.
precisa
52

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.

rgettman
fonte
As escalas sendo diferentes são a parte importante. Você pode escrever (em decimal) os valores exatos que estão sendo representados em binário como as entradas e ainda ter o mesmo problema.
perfil completo de Jon Skeet
@rgettman Como programador, eu gosto mais da sua resposta =)+1 para o seu ajudante de impressora hexadecimal ... isso é realmente legal!
ADTC
44

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!

Eric Lippert
fonte
Como você define uma grande quantidade? Estamos falando da ordem dos milésimos? 100ths? 1's ???
Cruncher
3
@ Cruncher: Calcule o resultado matemático exato e os valores x1 e x2. Chame a diferença matemática exata entre os resultados verdadeiros e os computados e1 e e2. Agora, existem várias maneiras de pensar sobre o tamanho do erro. A primeira é: você pode encontrar um cenário em que | e1 / e2 ou | e2 / e1 são grandes? Como, você pode cometer o erro de um dez vezes o erro do outro? O mais interessante, porém, é se você pode cometer o erro de uma fração significativa do tamanho da resposta correta.
precisa
1
Sei que ele está falando sobre tempo de execução, mas me pergunto: se a expressão era uma expressão em tempo de compilação (digamos, constexpr), os compiladores são inteligentes o suficiente para minimizar o erro?
Kevin Hsu
@ Kevinhsu em geral não, o compilador não é tão inteligente. Obviamente, o compilador pode optar por executar a operação com aritmética exata, se assim o desejar, mas geralmente não o faz.
22813 Eric
8
@frozenkoi: Sim, o erro pode ser infinito com muita facilidade. Por exemplo, considere o C #: double d = double.MaxValue; Console.WriteLine(d + d - d - d); Console.WriteLine(d - d + d - d);- a saída é Infinito, então 0.
Jon Skeet
10

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.

Bússola
fonte
9

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.

jbx
fonte
6

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)
hotforfeature
fonte
4
Eu acho que essa resposta evita a verdadeira razão. "existe um passo secundário em que números de ponto flutuante podem sair". Claramente, isso é verdade, mas o que queremos explicar é o porquê .
Zong