39

想象一下，您有大量各种大小的浮点数。计算总和的最正确方法是什么，并且误差最小？例如，当数组看起来像这样时：

[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<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;
    }
}
4

5 回答 5

24

对于“更精确”：Python Cookbook 中的这个配方有求和算法，可以保持完整的精度（通过跟踪小计）。代码是用 Python 编写的，但即使您不了解 Python，它也足以适应任何其他语言。

本文给出了所有细节。

于 2008-12-26T19:46:02.060 回答
15

另请参阅：Kahan 求和算法它不需要 O(n) 存储，而只需要 O(1)。

于 2009-01-27T22:30:56.523 回答
5

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

请注意，除了您的问题之外，对不同符号的数量求和是非常有问题的。

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

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

个人经验表明，你通常不需要比 Kahan 的方法更花哨的东西。

于 2010-12-30T14:07:55.103 回答
0

好吧，如果你不想排序，那么你可以简单地将总数保存在一个比单个值精度更高的变量中（例如，使用双精度来保持浮点数的总和，或者使用“四边形”来保持双打之和）。这会造成性能损失，但可能低于排序成本。

于 2008-12-26T21:02:12.267 回答
0

如果您的应用程序依赖于数值处理搜索任意精度的算术库，但是我不知道是否有这种 Python 库。当然，这一切都取决于您想要多少精度数字——如果您小心使用它，您可以使用标准 IEEE 浮点获得良好的结果。

于 2008-12-26T21:09:21.470 回答