我怎样才能以不同的顺序添加花车，并总是得到相同的总和？ [英] How can I add floats together in different orders, and always get the same total?

问题描述

假设我有三个32位浮点值，分别是 a ， b 和 c ，使得（a + b）+ c！= a +（b + c）。是否有一个求和算法，可能类似于 Kahan summation ，即保证这些数值可以按任何顺序加总，总是达到完全相同的（相当准确的）总数？我正在寻找一般情况下（即不是一个解决方案，只能处理3个数字）。

是任意的精度算术唯一的路要走吗？我正在处理非常大的数据集，所以我想避免使用任意精度算术的开销。如果可能的话。

谢谢！

解决方案

有一个有趣的全精度求和算法 msum recipe），为了得到正确舍入的结果，需要比单纯地求和部分和更加小心。看看配方下面的注释，以及Python的实现（下面链接）来解决这个问题。

$ b 它 使用任意形式用于保存部分和的精度算术（中间和表示为非重叠的双精度和），但是可能足够快，尤其是当所有的输入具有大致相同的幅度时。它总是给出一个正确的四舍五入的结果，所以准确性是你所期望的那样好，最后的总和独立于加数的次序。它基于这篇论文（Adaptive Precision Floating-Point算术和快速稳健的几何谓语）Jonathan Shewchuk。

Python使用这种算法来实现math.fsum，它能正确舍入顺序无关的求和。您可以看到Python使用的C实现 here a> ---查找math_fsum函数。

Let's say I have three 32-bit floating point values, a, b, and c, such that (a + b) + c != a + (b + c). Is there a summation algorithm, perhaps similar to Kahan summation, that guarantees that these values can be summed in any order and always arrive at the exact same (fairly accurate) total? I'm looking for the general case (i.e. not a solution that only deals with 3 numbers).

Is arbitrary precision arithmetic the only way to go? I'm dealing with very large data sets, so I'd like to avoid the overhead of using arbitrary precision arithmetic if possible.

Thanks!

解决方案

There's an interesting 'full-precision-summation' algorithm here, which guarantees that the final sum is independent of the order of the summands (recipe given in Python; but it shouldn't be too difficult to translate to other languages). Note that the recipe as given in that link isn't perfectly correct: the main accumulation loop is fine, but in the final step that converts the list of accumulated partial sums to a single floating-point result (the very last line of the msum recipe), one needs to be a little bit more careful than simply summing the partial sums in order to get a correctly-rounded result. See the comments below the recipe, and Python's implementation (linked below) for a way to fix this.

It does use a form of arbitrary-precision arithmetic to hold partial sums (the intermediate sums are represented as 'non-overlapping' sums of doubles), but may nevertheless be fast enough, especially when all the inputs are of roughly the same magnitude. And it always gives a correctly rounded result, so accuracy is as good as you could hope for and the final sum is independent of the order of the summands. It's based on this paper (Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates) by Jonathan Shewchuk.

Python uses this algorithm for its implementation of math.fsum, which does correctly-rounded order-independent summation; you can see the C implementation that Python uses here--- look for the math_fsum function.

这篇关于我怎样才能以不同的顺序添加花车，并总是得到相同的总和？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！