假设我有三个 32 位浮点值，a、b和c，这样(a + b) + c != a + (b + c). 是否有一种求和算法，可能类似于Kahan summation，可以保证这些值可以按任何顺序求和并且总是达到完全相同（相当准确）的总数？我正在寻找一般情况（即不是只处理 3 个数字的解决方案）。
任意精度算术是唯一的方法吗？我正在处理非常大的数据集，所以如果可能的话，我想避免使用任意精度算术的开销。
谢谢！
问问题
2786 次
3 回答
10
这里有一个有趣的“全精度求和”算法，它保证最终总和独立于和的顺序（Python 中给出的配方；但翻译成其他语言应该不会太难）。请注意，该链接中给出的配方并不完全正确：主累加循环很好，但在将累加部分和列表转换为单个浮点结果的最后一步（msum配方的最后一行)，为了得到正确舍入的结果，需要比简单地对部分和求和更加小心。有关解决此问题的方法，请参阅配方下方的注释和 Python 的实现（链接如下）。
它确实使用一种任意精度的算术形式来保存部分和（中间和表示为双精度的“非重叠”和），但可能仍然足够快，尤其是当所有输入的大小大致相同时。它总是给出正确舍入的结果，因此准确度与您希望的一样好，并且最终总和与被加数的顺序无关。它基于 Jonathan Shewchuk 的这篇论文（Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates）。
Python 使用这个算法来实现 math.fsum，它执行正确舍入的与顺序无关的求和；您可以在此处看到 Python 使用的 C 实现--- 查找 math_fsum 函数。
于 2010-04-24T13:14:31.760 回答
3
通过一些关于必须求和的项的附加信息，您可以避免 Shewchuk 算法的开销。
在 IEEE 754 算术中，x-y无论何时都是精确的y/2 <= x <= 2*y（Sterbenz 定理，此处正式证明）
因此，如果您可以按顺序排列所有条款，使得每个部分总和都具有上述形式，那么您就可以免费获得确切的结果。
恐怕在实践中，这种情况肯定会发生的可能性很小。以增加的幅度交替正数和负数可能是它发生的一种情况。
注意：最初的问题是关于一种不管求和顺序如何都会给出相同结果的算法。马克的回答引发了“精确算法”方向的漂移，但再次阅读您的问题，恐怕当我建议重新排序术语时，我把事情推得太远了。你可能不能做你想做的事，我的回答可能是题外话。好吧，对不起：）
于 2010-04-24T21:49:57.717 回答
-3
在程序中进行算术运算时，我不太确定 (a + b) + c != a + (b + c) 。
然而，在当今硬件上使用浮点运算的经验法则是永远不要直接测试是否相等。
对于您拥有的任何应用程序，您应该选择一个足够小的 epsilon 并使用
(abs(a - b) < epsilon)
作为平等检验。
于 2010-04-24T12:04:27.080 回答