java - lintcode github




为什么更改总和顺序会返回不同的结果? (5)

也许这个问题很愚蠢,但为什么简单地改变元素的顺序会影响结果呢?

它会根据数值的大小改变数值四舍五入的点。 作为我们看到的那种事情的一个例子,让我们假装代替二进制浮点,我们使用了一个有四位有效数字的十进制浮点类型,其中每个加法以“无限”精度执行,然后舍入为最接近的可表示数字。 这里有两个总和:

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精度值很重要,由于上述问题,这只是一个问题。

为什么更改总和顺序会返回不同的结果?

23.53 + 5.88 + 17.64 = 47.05

23.53 + 17.64 + 5.88 = 47.050000000000004

JavaJavaScript返回相同的结果。

我明白,由于浮点数的方式是用二进制表示的,所以有些有理数( 比如1/3 - 0.333333 ... )不能精确表示。

为什么简单地改变元素的顺序会影响结果?


乔恩的答案当然是正确的。 在你的情况下,错误不会大于你要做任何简单的浮点运算所积累的错误。 你有一种情况,在一种情况下,你得到零误差,而在另一种情况下,你会得到一个小错误; 这实际上并不是那种有趣的场景。 一个很好的问题是: 是否有改变计算顺序的情景从一个微小的错误变成一个(相对)巨大的错误? 答案毫无疑问是肯定的。

考虑例如:

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;

显然,在精确的算术中它们将是相同的。 试图找出a,b,c,d,e,f,g,h的值,使得x1和x2和x3的值相差很大是有趣的。 看看你是否可以这样做!


我相信它与顺序的排序有关。 虽然这个总和在数学世界中自然是相同的,但在二元世界中,而不是A + B + C = D,它是相同的

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

所以有浮点数可以下的第二步。

当你改变订单时,

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

浮点数用IEEE 754格式表示,该格式为尾数(有效数)提供特定的比特大小。 不幸的是,这给你一个特定数量的“小数积木”来玩,某些小数值不能精确表示。

你的情况发生的是,在第二种情况下,由于添加的评估顺序,添加可能会遇到一些精确问题。 我没有计算出这些值,但可能是23.53 + 17.64不能精确表示,23.53 + 5.88可以。

不幸的是,这是一个已知的问题,你只需要处理。


这是二进制发生了什么。 正如我们所知,一些浮点值不能完全用二进制表示,即使它们可以完全用十进制表示。 这3个数字就是这个事实的例子。

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

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

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个数字是xyzs的十六进制表示。 在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 + yz并添加两个相同比例的数字。

第二组添加

这里, x + z首先出现。 它们具有相同的规模,但是它们产生的规模更高:

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

第二个加法增加了x + zy ,现在3个比特从y中删除以添加数字( 101 )。 这里,必须向上舍入,因为结果是下一个浮点数:第一组添加4047866666666667 ,而第二组添加4047866666666667 。 该错误足以显示总数的打印结果。

总之,在对IEEE数字进行数学运算时要小心。 一些表述是不精确的,当尺度不同时它们变得更加不精确。 如果可以的话,加减相似比例的数字。





floating-point