あらゆる種類のサイズの浮動小数点数の大きな配列があるとします。誤差が最も少なく、合計を計算する最も正しい方法は何ですか? たとえば、配列が次のようになっている場合:
[1.0, 1e-10, 1e-10, ... 1e-10.0]
次のような単純なループで左から右に合計します
sum = 0
numbers.each do |val|
sum += val
end
小さい数値を合計すると、精度のしきい値を下回る可能性があるため、エラーがどんどん大きくなります。私の知る限り、最良の方法は、配列を並べ替えて、数値を最小から最大に加算することですが、もっと良い方法 (より速く、より正確) があるかどうか疑問に思っています。
編集：答えてくれてありがとう、Javaでdouble値を完全に合計する作業コードができました。これは、勝利した回答の 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;
}
}