std::partial_sum 和 Kahan 算法

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());

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

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 求和：

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）。