std::partial_sum 和 where 算法

Question

在 C++11 中，我想使用 std::partial_sum 计算向量的部分和。

std::vector<double> vec = {-1.0, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1};
std::partial_sum(vec.begin(), vec.end(), vec.begin());

不幸的是，结果向量的最后一个条目是 1.38778E-16，这是由于双精度的舍入误差以及 0.1 没有准确表示为双精度的事实。

vec = {-1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1, 1.38778E-16};

是否有机会在 std::partial_sum 中使用 Kahan 算法来减少舍入误差并获得更小的误差 - 类似于

std::partial_sum(vec.begin(), vec.end(), vec.begin(), KahanSum);

Answer 1

你可以在std::partial_sum之上实现Kahan求和（基于Wikipedia pseudocode）：

double c = 0.0;
std::partial_sum(vec.begin(), vec.end(), vec.begin(),
        [c](double sum, double elem) mutable -> double {
            double y = elem - c;
            double t = sum + y;
            c = (t - sum) - y;
            return t;
        });

这仍然不会让你归零，因为 (double)0.1 正好等于 0.1000000000000000055511151231257827021181583404541015625 所以你的数组的确切总和约为 5.5511151231E-17（假设标准 double）。

std::partial_sum 和 where 算法

std::partial_sum and Kahan algorithm

algorithm

stl

c++11