如何最好地总结大量的浮点数？

想象一下,你有各种各样大小的浮点数.计算总和的最正确方法是什么,误差最小？例如,当数组看起来像这样:

[1.0, 1e-10, 1e-10, ... 1e-10.0]

然后你用一个简单的循环从左到右加起来,比如

sum = 0
numbers.each do |val|
    sum += val
end

无论何时加起来,较小的数字可能会低于精度阈值,因此误差会越来越大.据我所知,最好的方法是对数组进行排序并开始将数字从最低到最高相加,但我想知道是否有更好的方法(更快,更精确)？

编辑:谢谢你的答案,我现在有一个工作代码,完美地总结了Java中的双重值.它是获胜答案的Python帖子的直接端口.该解决方案通过了我的所有单元测试.(这里有更长但优化的版本Summarizer.java)

/**
 * Adds up numbers in an array with perfect precision, and in O(n).
 * 
 * @see http://code.activestate.com/recipes/393090/
 */
public class Summarizer {

    /**
     * Perfectly sums up numbers, without rounding errors (if at all possible).
     * 
     * @param values
     *            The values to sum up.
     * @return The sum.
     */
    public static double msum(double... values) {
        List partials = new ArrayList();
        for (double x : values) {
            int i = 0;
            for (double y : partials) {
                if (Math.abs(x) < Math.abs(y)) {
                    double tmp = x;
                    x = y;
                    y = tmp;
                }
                double hi = x + y;
                double lo = y - (hi - x);
                if (lo != 0.0) {
                    partials.set(i, lo);
                    ++i;
                }
                x = hi;
            }
            if (i < partials.size()) {
                partials.set(i, x);
                partials.subList(i + 1, partials.size()).clear();
            } else {
                partials.add(x);
            }
        }
        return sum(partials);
    }

    /**
     * Sums up the rest of the partial numbers which cannot be summed up without
     * loss of precision.
     */
    public static double sum(Collection values) {
        double s = 0.0;
        for (Double d : values) {
            s += d;
        }
        return s;
    }
}

dF... 24

对于"更精确":Python Cookbook中的这个配方具有总和算法,可以保持完整的精度(通过跟踪小计).代码在Python中,但即使您不了解Python,它也足以适应任何其他语言.

所有细节都在本文中给出.

对于"更精确":Python Cookbook中的这个配方具有总和算法,可以保持完整的精度(通过跟踪小计).代码在Python中,但即使您不了解Python,它也足以适应任何其他语言.

所有细节都在本文中给出.

另请参见:Kahan求和算法它不需要O(n)存储,只需要O(1).