为什么改变求和顺序会得到不同的结果?

310
为什么改变相加顺序会返回不同的结果? 23.53 + 5.88 + 17.64 = 47.05 23.53 + 17.64 + 5.88 = 47.050000000000004 无论是Java还是JavaScript都会返回相同的结果。
我了解由于浮点数在二进制中的表示方式,一些有理数(如1/3 - 0.333333...)不能精确地表示。
为什么只是改变元素的顺序就会影响结果呢?

30
实数的和是可交换和结合的。浮点数不是实数。事实上,你刚刚证明了它们的运算不是可交换的。很容易证明它们也不是可结合的(例如,(2.0^53 + 1) - 1 == 2.0^53 - 1 != 2^53 == 2^53 + (1 - 1))。因此,在选择求和和其他操作的顺序时要小心。一些编程语言提供了内置函数来执行“高精度”求和运算(例如Python中的 math.fsum),因此您可以考虑使用这些函数而不是朴素的求和算法。 - Bakuriu
1
@RBerteig 这可以通过检查语言中算术表达式的操作顺序来确定,除非它们在内存中表示浮点数的方式不同,否则如果它们的运算符优先级规则相同,则结果将相同。另一个值得注意的地方是:我想知道开发银行应用程序的开发人员花了多长时间才能弄清楚这一点?那些额外的 0000000000004 美分真的会累加起来! - Chris Cirefice
3
如果你手头只有0.00000004美分,那么你做错了。在财务计算中,你绝对不应该使用二进制浮点数类型。请注意,这句话的意思是不要用浮点数来表示金融数据。 - Daniel Pryden
2
@DanielPryden 啊,遗憾啊,这只是一个玩笑……只是随便提出一个想法,那些真正需要解决这种问题的人有着最重要的工作,你知道的,掌握着人民的货币状况和所有其他方面。我当时非常的讽刺…… - Chris Cirefice
6
非常干燥(而且有点陈旧,但仍然相关):计算机科学家应该了解的浮点数算术知识 - Brian
显示剩余6条评论
8个回答

282
也许这个问题很愚蠢,但是为什么简单地改变元素的顺序会影响结果呢?
它将改变值舍入的位置,取决于它们的大小。举一个例子,假设我们不是使用二进制浮点数,而是使用四位有效数字的十进制浮点数类型,每次加法都在“无限”精度下执行,然后舍入到最接近的可表示数字。这里有两个和:
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)

我们甚至不需要非整数也可能出现这样的问题:
10000 + 1 - 10000 = (10000 + 1) - 10000
                  = 10000 - 10000 (where 10001 is rounded to 10000)
                  = 0

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

这更清楚地说明了重要的部分是我们有限的“有效数字”而不是有限的“小数位数”。如果我们总能保持相同数量的小数位,那么至少在加法和减法方面,我们就没有问题(只要值不溢出)。问题在于当你处理更大的数字时,较小的信息会丢失 - 在这种情况下,10001被舍入为10000。(这是Eric Lippert在他的答案中指出的问题的示例。)
重要的是要注意,在右侧第一行的值在所有情况下都是相同的 - 因此,尽管重要的是要理解您的小数(23.53、5.88、17.64)不会被表示为精确的double值,但这只是因为上述问题所示的问题。

10
现在时间有点不够,待会儿可能会继续延长!迫不及待地等待着 @Jon。 - Prateek
3
当我说我会稍后回答时,社区对我不太友好。 <插入一些轻松幽默的表情符号来展现我是在开玩笑而不是粗鲁的人>...稍后再回来看这个。 - Grady Player
2
@ZongZhengLi:虽然理解这一点确实很重要,但在这种情况下并不是根本原因。你可以写一个类似的例子,其中的值在二进制中确实被准确表示,并且会得到相同的效果。问题在于同时维护大规模信息和小规模信息。 - Jon Skeet
1
但是@JonSkeet,一个只能存储4个有效数字的数据类型应该会导致溢出而不是将数字四舍五入到最高位。我理解浮点数尾数的论点,但我不明白为什么1001会被四舍五入到1000。您能详细解释一下吗? - meteors
3
@meteors:不会发生溢出,而且你使用了错误的数字。是将10001四舍五入到10000,而不是将1001四舍五入到1000。为了让它更清楚,54321会被四舍五入为54320——因为只有四个有效数字。"四个有效数字"和"最大值为9999"之间有很大的区别。就像我之前说的,你基本上代表着x.xxx * 10^n,对于10000,x.xxx应该是1.000,n应该是4。这就像“double”和“float”,在非常大的数字中,连续的可表示数字相差超过1。 - Jon Skeet
显示剩余7条评论

52

以下是二进制中正在发生的情况。我们知道,一些浮点数在二进制下无法准确表示,即使它们在十进制下可以准确表示。这三个数字只是这个事实的例子。

通过这个程序,我输出了每个数字的十六进制表示以及每个加法的结果。

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);
   }
}
< p > printValueAndInHex 方法只是一个帮助程序员打印十六进制的辅助工具。

输出如下:

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

前4个数字是x, y, z, 和 s 的十六进制表示。在IEEE浮点表示中,位2-12代表二进制的指数,即该数值的比例尺。 (第一位是符号位,其余位用于小数部分。)实际上表示的指数是二进制数减去1023。

前4个数字的指数已被提取:

    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

第一组加法

第二个数字(y)的幅度较小。当将这两个数字相加得到(x+y)时,第二个数字(01)的最后2位被移出范围,不参与计算。

第二次加法是将(x+y)和z相加,并添加两个相同幅度的数字。

第二组加法

这里,首先进行的是(x+z)的相加。它们具有相同的幅度,但产生的结果在更高的幅度上:

404 => 0|100 0000 0100| => 1028 - 1023 = 5
第二次修改添加了x+zy,现在从y中减去3位来加上数字(101)。在这里,必须向上舍入,因为结果是下一个浮点数的上限:4047866666666666对于第一组加法,而4047866666666667对于第二组加法。这个误差足以在总输出中显示。
总之,在IEEE数值上进行数学运算时要小心。有些表示是不精确的,当比例不同时,它们变得更不精确。如果可以,请加减具有相似比例的数字。

不同的比例尺是重要的部分。你可以用十进制写出被表示为二进制输入的确切值,但仍然会有相同的问题。 - Jon Skeet
作为一名程序员,我更喜欢你的答案 =) ,你的十六进制打印机助手真的很棒! - ADTC

44

乔恩的回答当然是正确的。在您的情况下,错误不会比执行任何简单浮点运算积累的误差更大。您面临的情况是,在某些情况下,您获得零误差,而在另一种情况下,您获得微小误差;实际上这并不是一个非常有趣的情况。一个好问题是:是否存在一些情况,其中改变计算顺序会从微小误差变为(相对)巨大的误差? 答案毫无疑问是肯定的。

例如考虑:

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

对抗

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

对阵

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

显然,在精确计算中它们是相同的。尝试找到a,b,c,d,e,f,g,h的值,使得x1、x2和x3的值之间有很大的差异,这很有趣。看看你能否做到!


你如何定义大量?我们是指1000个,100个还是1个数量级? - Cruncher
3
@Cruncher:计算出精确的数学结果和x1和x2的值。将实际结果与计算结果之间的精确数学差异称为e1和e2。现在有几种思考误差大小的方法。第一种是:您能否找到一种情况,使得| e1 / e2 |或| e2 / e1 |很大?比如说,你可以让一个错误是另一个错误的十倍吗?然而更有趣的是,如果您可以使其中一个误差成为正确答案大小的显著部分。 - Eric Lippert
1
我意识到他在谈论运行时,但我想知道:如果表达式是编译时(比如constexpr)表达式,编译器是否足够聪明以最小化错误? - Kevin Hsu
一般来说,编译器并不那么聪明。当然,如果编译器选择这样做,它可以选择在精确算术中执行操作,但通常不会这样做。 - Eric Lippert
8
是的,这个错误很容易变成无限大。例如,考虑C#语言中的代码:double d = double.MaxValue; Console.WriteLine(d + d - d - d); Console.WriteLine(d - d + d - d); - 输出结果为Infinity和0。 - Jon Skeet
显示剩余3条评论

10

这实际上涵盖了不仅仅是Java和Javascript,而且可能会影响使用浮点数或双精度浮点数的任何编程语言。

在内存中,浮点数使用类似于IEEE 754的特殊格式(转换器提供了比我更好的解释)。

无论如何,这是一个浮点数转换器。

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

关于操作顺序的问题是操作的“精细程度”。

您的第一行从前两个值中得出29.41,这使我们的指数为2 ^ 4。

您的第二行产生41.17,这使我们的指数为2 ^ 5。

通过增加指数,我们失去了一个有效数字,这很可能会改变结果。

尝试在41.17上打开和关闭最右边的最后一位,您可以看到像1/2 ^ 23这样“微不足道”的东西足以引起这种浮点差异。

编辑:对于那些记得有效数字的人来说,这将属于该类别。10 ^ 4 + 4999的有效数字为1,将成为10 ^ 4。在这种情况下,有效数字要小得多,但我们可以看到附加的.00000000004带来的结果。


9
浮点数使用IEEE 754格式表示,其中为尾数(有效数字)提供了特定大小的比特。不幸的是,这给你提供了一定数量的小数部分构建块,并且某些小数值无法精确表示。
在您的情况下发生的情况是,在第二个情况下,由于执行加法的顺序,可能会遇到某些精度问题。我没有计算过值,但例如23.53 + 17.64可能无法精确表示,而23.53 + 5.88可以精确表示。
很遗憾,这是一个已知的问题,您只能处理它。

7

我认为这与计算顺序有关。虽然在数学世界中,总和自然相同,但在二进制世界中,A + B + C = D 被转换为

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

因此,有一个次要步骤,浮点数可能会出现偏差。

当您更改顺序时,

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

4
我认为这个答案回避了真正的原因。“有一个次要的步骤,浮点数可能会出错”。显然,这是正确的,但我们想要解释的是为什么 - Zong

0
为了给其他答案增加不同的角度,这个SO答案展示了有一些浮点数计算的方法,其中所有求和顺序在位级别上返回完全相同的值。

0
问题在于有限精度。这意味着您需要在每个操作中进行四舍五入。
一个例子(使用Python)是:
>>> 0.1 + 0.2 + 0.3
0.6000000000000001

>>> 0.2 + 0.3 + 0.1
0.6

这归结于你舍入的位置。使用Decimal包时也会遇到同样的问题。以下是一个Python示例:

>>> from decimal import Decimal, get_context
>>> getcontext().prec = 1

>>> Decimal("0.11") + Decimal("0.23") + Decimal("0.33")
Decimal('0.6')

>>> Decimal("0.11") + (Decimal("0.23") + Decimal("0.33"))
Decimal('0.7')

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接