如何最好地总结了很多浮点的数字？

Question

想象一下，你有一个大型阵列的浮点数的所有种类的大小。什么是最正确的方法来计算的总和，用最少的错误？例如，当列看起来是这样的：

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

和你加起来，从左到右有一个简单的循环，就像

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

只要您添加了更小的数字有可能下降的精度阈值，因此错误得到越来越大。就我所知道的最好办法是进行排列，并开始增加了人数，从最低到最高的，但我想知道如果有一个更好的方法(更快、更精确的)?

编辑:谢谢你的回答，我现在有一个代码的工作完美地总结了双值。这是一个直口从Python后的赢得的答案。该方案通过我的所有单元的测试。(A较长，但优化版本，这是可以在这里 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<Double> partials = new ArrayList<Double>();
        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<Double> values) {
        double s = 0.0;
        for (Double d : values) {
            s += d;
        }
        return s;
    }
}

Answer 1

对于"更加精确的": 这个配方的蟒蛇的食谱 已经求和算法，它保持全面精确度(通过跟踪的小计).代码是在Python但即使如果你不知道蟒蛇很明显的，足以适应任何其他语言。

所有的细节 这纸.

Answer 2

参见： Kahan的求和算法它不需要ö （n）的存储，但只有O（1）。

Answer 3

算法有很多种，看你想要什么。通常他们需要跟踪部分金额。如果你只保留 x[k+1] - x[k] 的和，你就得到了 Kahan 算法。如果您跟踪所有部分和（因此产生 O(n^2) 算法），您会得到 @dF 的答案。

请注意，除了您的问题之外，还要对 不同的标志 是很有问题的。

现在，有比跟踪所有部分和更简单的方法：

• 求和之前对数字进行排序，将所有负数和正数独立相加。如果你已经对数字进行了排序，那很好，否则你就有 O(n log n) 算法。通过增加幅度求和。
• 按对求和，然后对对求和，等等。

个人经验表明，您通常不需要比卡汉的方法更奇特的东西。

Answer 4

好吧，如果你不想排序，那么你可以简单地总保持有型的比单个数值精度高的变量（例如使用双保持浮动的总和，或者“四”保持双打的总和）。这将对性能损失，但也可能是小于排序的成本。

Answer 5

如果您的应用程序依赖于数字处理搜索的高精度计算库，但我不知道是否有这样的Python库。当然，一切都取决于你想要多少精度数字 - 如果你小心使用它，你可以实现与标准的IEEE浮点良好的效果。