Namaran

Code daily. Without assist.

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 がまとめて足されます。