假设您有一个很大的浮点数数组,各种大小。哪种计算和的方法最正确,误差最小?例如,当数组如下所示时:
[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;
}
}
另请参见:Kahan summation algorithm它不需要O(n)存储,而只需要O(1)。
有很多算法,取决于你想要什么。通常他们需要跟踪部分和。如果只保留和x[k+1]-x[k],就得到Kahan算法。如果你跟踪所有的部分和(因此产生O(n^2)算法),你会得到@dF的答案。
请注意,除了您的问题之外,将不同符号的数目相加是非常有问题的。
现在,有比跟踪所有部分和更简单的方法:
个人经验表明,你通常不需要比卡恩的方法更华丽的东西。
对于“更精确”:this recipe in the Python Cookbook有求和算法,可以保持完全的精度(通过跟踪小计)。代码是用Python编写的,但即使您不了解Python,也可以很清楚地适应任何其他语言。
所有细节都在this paper中给出。
相关问题 更多 >
编程相关推荐