代码之家 › 专栏 › 技术社区 › splicer

如何将浮点数按不同的顺序相加,并始终得到相同的总数?

numerical math floating-point

5

splicer · 技术社区 · 15 年前

假设我有三个32位浮点值, a , b 和 c ,这样 (a + b) + c != a + (b + c) . 是否有一个求和算法,可能类似于 Kahan summation ,这就保证了这些值可以按任意顺序求和,并且总是得到完全相同(相当准确)的总和?我在找一般情况(即不是只处理3个数字的解决方案)。

任意精度算术是唯一的方法吗?我处理的是非常大的数据集,因此我希望尽可能避免使用任意精度算法的开销。

谢谢!

3 回复 | 直到 10 年前

1

8

Mark Dickinson Alexandru 10 年前

有一个有趣的“全精度求和”算法 here 这就保证了最终的和独立于和的顺序(用python给出的方法;但是不应该太难翻译成其他语言)。请注意,该链接中给出的方法并不完全正确:主累积循环很好,但在将累积部分和列表转换为单个浮点结果的最后一步( msum 方法),我们需要比简单地求和部分和更小心一点,以便得到正确的四舍五入结果。请参阅配方下面的注释,以及python的实现(链接在下面),了解解决此问题的方法。

它做使用任意精度的算术形式来保存部分和(中间和表示为“不重叠”的双精度和),但可能足够快,尤其是当所有输入的大小大致相同时。它总是给出一个正确的四舍五入结果,所以准确度是你所希望的,最后的和独立于和的顺序。它是基于 this paper (自适应精度浮点运算和快速鲁棒的几何谓词)作者:Jonathan Sheuchuk。

python将此算法用于math.fsum的实现,math.fsum可以正确地舍入与顺序无关的求和;您可以看到python使用的C实现 here ---寻找数学函数。

2

Pascal Cuoq 15 年前

有了一些关于必须求和的术语的附加信息,就可以避免sheuchuk算法的开销。

在IEEE754算法中, x-y 无论何时 y/2 <= x <= 2*y (斯特本斯定理,正式证明) here )

所以,如果你能把所有的条件排列成这样的顺序,每一个部分和都是上面的形式,那么你就可以免费得到确切的结果。

我担心,在实践中,很少有机会处于可以保证发生这种情况的条件下。随着震级的增加,正负数交替出现可能是一种情况。

注:最初的问题是关于一种算法,它可以给出相同的结果,而不管求和顺序如何。马克的回答开始向“精确算法”的方向漂移,但再次阅读你的问题,恐怕我在建议重新排序术语时把事情推得太远了。你可能做不到你想做的事情,我的答案可能是离题的。哦,对不起:)

3

-1

rep_movsd 15 年前

我不太确定(A+B)+C!=A+(B+C)在程序中执行算术时。

然而,目前硬件上使用浮点运算的经验法则是永远不要直接测试是否相等。

无论您有什么应用程序,您都应该选择一个足够小的epsilon并使用

(abs(a - b) < epsilon)

作为平等测试。