如何最好地总结大量浮点数? [英] How best to sum up lots of floating point numbers?

问题描述

想象一下，您有大量各种大小的浮点数数组.计算总和的最正确方法是什么，并且误差最小?例如，当数组如下所示时:

Imagine you have a large array of floating point numbers, of all kinds of sizes. What is the most correct way to calculate the sum, with the least error? For example, when the array looks like this:

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

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

and you add up from left to right with a simple loop, like

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

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

whenever you add up the smaller numbers might fall below the precision threshold so the error gets bigger and bigger. As far as I know the best way is to sort the array and start adding up numbers from lowest to highest, but I am wondering if there is an even better way (faster, more precise)?

编辑:感谢您的回答，我现在有一个工作代码可以完美地总结 Java 中的双精度值.它是来自获胜答案的 Python 帖子的直接端口.该解决方案通过了我所有的单元测试.(此处提供了更长但优化的版本 Summarizer.java)

EDIT: Thanks for the answer, I now have a working code that perfectly sums up double values in Java. It is a straight port from the Python post of the winning answer. The solution passes all of my unit tests. (A longer but optimized version of this is available here 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;
    }
}

推荐答案

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

For "more precise": this recipe in the Python Cookbook has summation algorithms which keep the full precision (by keeping track of the subtotals). Code is in Python but even if you don't know Python it's clear enough to adapt to any other language.

所有细节都在 这篇论文.

这篇关于如何最好地总结大量浮点数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！