假设我有三个 32 位浮点值:a、b 和 c，这样 (a + b) + c != a + (b + c)。是否有求和算法，可能类似于 Kahan summation ，这保证了这些值可以以任何顺序求和并且始终得到完全相同(相当准确)的总数？我正在寻找一般情况(即不是只处理 3 个数字的解决方案)。
任意精度算术是唯一的方法吗？我正在处理非常大的数据集，因此我希望尽可能避免使用任意精度算术的开销。
谢谢!
最佳答案
有一个有趣的“全精度求和”算法 here ，这保证了最终的总和与被加数的顺序无关(Python 中给出的方法；但翻译成其他语言应该不会太困难)。请注意，该链接中给出的配方并不完全正确:主累加循环很好，但在最后一步将累加部分和列表转换为单个浮点结果(msumrecipe)，为了得到正确舍入的结果，需要比简单地对部分和求和更加小心。请参阅配方下面的注释以及 Python 的实现(下面链接)以获取解决此问题的方法。
它确实使用某种形式的任意精度算术来保存部分和(中间和表示为 double 的“非重叠”和)，但仍然可能足够快，特别是当所有输入的大小大致相同。它总是给出正确的舍入结果，因此准确性与您所希望的一样好，并且最终的总和与被加数的顺序无关。它基于this paper (自适应精度浮点算术和快速鲁棒几何谓词)作者:Jonathan Shewchuk。
Python 使用此算法来实现 math.fsum，它可以正确舍入与顺序无关的求和；你可以看到Python使用的C实现here --- 查找 math_fsum 函数。
关于floating-point - 如何以不同的顺序将 float 相加，并始终得到相同的总数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2704344/