2026-11-14
accurate_sum.cpp
#include <vector>
double accurate_sum(const std::vector<double>& xs) {
}
double の並び xs の総和を、足すたびに丸めで失われた分を取り戻しながら求める accurate_sum を書いてください。絶対値の大きい値と小さい値がどの順に並んでいても、入力例1が 1.0 の2つ分、つまり 2 になるようにします。xs が空なら 0 を返します。出力例は、返り値を std::println("{}", ...) で出したものです。
入力例 1
accurate_sum({1.0, 1e100, 1.0, -1e100})
出力例 1
2
入力例 2
accurate_sum({})
出力例 2
0
入力例 3
accurate_sum({1e16, 1.0, 1.0})
出力例 3
10000000000000002
Reference
Reference
double accurate_sum(const std::vector<double>& xs) {
double sum = 0.0;
double lost = 0.0;
for (double x : xs) {
double t = sum + x;
if (std::abs(sum) >= std::abs(x)) {
lost += (sum - t) + x;
} else {
lost += (x - t) + sum;
}
sum = t;
}
return sum + lost;
}
t = sum + x で失われるのは、2つのうち絶対値の小さい方の下位の桁です。大きい方から t を引くと、和に実際に入った小さい方の分が残ります。それを小さい方から引けば、入りきらなかった分が正確に求まります。参考実装は、|sum| >= |x| なら (sum - t) + x を、そうでなければ (x - t) + sum を、失った分として lost に足していきます。最後に sum + lost を返すので、空の並びでは 0.0 + 0.0 で 0 です。掲載したのは参考実装で、唯一の正解ではありません。
よく知られた形では、失った分 c を次に足す値から先に引き(y = x - c)、c = (t - sum) - y で更新します。この式は sum の方が大きいと決め込んでいて、入力例1では 0 を返します。1つ目の 1.0 が入った sum に 1e100 を足すと、t - sum は 1e100 になり、そこから y の 1e100 を引いた c は 0 です。失われた 1.0 は c に記録されません。2つ目の 1.0 は c に残りますが、y = -1e100 - c を計算するときに -1e100 に吸収されて消えます。
参考実装では、1e100 を足すときに x の方が大きいので (x - t) + sum を使い、消えた 1.0 を lost に移します。2つ目の 1.0 も、sum が 1e100 のときに足されて (sum - t) + x で lost に入ります。-1e100 で sum が 0 に戻ったあと、lost の 2 を足して 2 を返します。入力例3も、1e16 に1つずつ足して消える 1.0 が lost にたまり、最後に 2 がまとめて足されます。