spl*_*cer 6 math floating-point numerical
比方说,我有3个32位浮点值,a,b,和c,这样(a + b) + c != a + (b + c).是否存在可能类似于Kahan求和的求和算法,它保证这些值可以按任何顺序求和并且总是达到完全相同(相当准确)的总和？我正在寻找一般情况(即不是仅涉及3个数字的解决方案).
是任意精度算术的唯一出路吗？我正在处理非常大的数据集,所以我希望尽可能避免使用任意精度算术的开销.
谢谢!
这里有一个有趣的"全精密求和"算法在这里,这保证了最终的总和独立加数的顺序(在Python定配方,但它不应该是太难翻译成其他语言).请注意,在该链接中给出的配方是不完全正确的:主力吸筹循环是好的,但在累积转换部分和一个单精度浮点结果列表(的最后一行的最后一步msum食谱),为了获得正确的舍入结果,需要比简单地求和部分和更加小心.请参阅配方下面的注释和Python的实现(下面链接)以获得解决此问题的方法.
它确实使用任意精度算术的形式来保持部分和(中间和表示为'非重叠'的双精度和),但仍然可以足够快,特别是当所有输入具有大致相同的幅度时.并且它总是给出一个正确的舍入结果,因此准确性与您希望的一样好,并且最终总和与加数的顺序无关.它基于Jonathan Shewchuk撰写的这篇论文(Adaptive Precision Floating-Point Arithmetic和Fast Robust Geometric Predicates).
Python使用这个算法来实现math.fsum,它可以正确舍入与顺序无关的求和; 你可以看到Python 在这里使用的C实现---查找math_fsum函数.