13

假设我们在10^(-15)中有一个小（大约）双精度数的数组。如果我们按顺序计算这个数组中数字的总和，例如

double sum = 0;
for (int i = 0; i < n; i++) sum+=array[i];

我们得到了一些价值x。

但是，如果我们将一个数组分成若干部分，然后计算每个部分的总和，然后将所有部分总和相加，我们会得到一些值x2，该值接近x但不完全x。所以我在计算总和时失去了准确性。

有人知道如何通过将这些数字分成一些部分来计算小双数的总和而不会失去准确性吗？

4

8 回答 8

19

使用卡汉求和：

#include <numeric>
#include <iostream>
#include <vector>

struct KahanAccumulation
{
    double sum;
    double correction;
};

KahanAccumulation KahanSum(KahanAccumulation accumulation, double value)
{
    KahanAccumulation result;
    double y = value - accumulation.correction;
    double t = accumulation.sum + y;
    result.correction = (t - accumulation.sum) - y;
    result.sum = t;
    return result;
}

int main()
{
    std::vector<double> numbers = {0.01, 0.001, 0.0001, 0.000001, 0.00000000001};
    KahanAccumulation init = {0};
    KahanAccumulation result =
        std::accumulate(numbers.begin(), numbers.end(), init, KahanSum);

    std::cout << "Kahan Sum: " << result.sum << std::endl;
    return 0;
}

输出：

Kahan Sum: 0.011101

代码在这里。

于 2012-04-26T09:39:49.160 回答
4

数字的绝对大小不是问题。

如果您想要更准确的总和，您是否考虑过补偿总和？http://en.wikipedia.org/wiki/Kahan_summation_algorithm

但是，如果您真的是在不损失任何准确性的情况下，您的结果不一定适合双精度数。如果这确实是您想要的，您可以在http://dl.acm.org/citation.cfm?id=1824815或类似网站上查看算法 908。

于 2012-04-26T09:04:30.383 回答
3

在这些情况下，诀窍是首先将数组从小到大排序，然后在您创建的循环中求和。这样，准确性最好。

您还可以检查Kahan 求和算法

于 2012-04-26T08:51:34.670 回答
2

考虑对整个集合或每个子集应用Kahan 求和算法。

还有其他问题可以参考这个算法，可以帮助你

于 2012-04-26T08:55:39.817 回答
1

计算机中的双精度数以二进制数字系统存储。这就是为什么当您看到一个双精度值（十进制表示法）时，您实际上会看到带有一些舍入的双精度值（例如 0.1 是无限小数）。您可以进行相同的实验，其中双精度值为 2（例如 2^(-30)），然后您将看到这些值将匹配。

将不同顺序的双精度值求和时观察到差异的原因是，每次计算后，结果都会以二进制数字系统四舍五入，因此与实际值会出现一点差异。

于 2012-04-26T08:50:47.050 回答
1

用于表示十进制数的二进制浮点数具有比准确性更高的精度。你已经找到了一种表现差异的方法。

于 2012-04-26T08:50:53.763 回答
1

可能是您的个人求和正在被优化并在 80 位的寄存器中执行，但随后又被转移回 64 个双精度数（阅读有关编译器开关的信息）。这自然会失去精度。如果是这种情况，那么分解数组并添加单独的 64 位和将给出不同的答案，将它们全部添加为 80 位 a 并将总计转换回来。

这可能不是原因，但可能值得进一步研究。看看这个问题的选择答案

于 2012-04-26T09:03:35.950 回答
0

在处理非常小的数字与处理正常大小的数字时，添加数字的结果中的精度损失没有什么不同。可能相关的是：a）数字之间的相对差异是否很大？b) 数字有不同的标志吗？

最后一个问题通常与加法精度有关。你应该做的——也许不是完全最优的，但是公平的，并且易于实施——是：

a) 分别将它们分成正负子集

b) 对每个子集进行排序

然后

c）从两个集合中取最大的（绝对大小），并用该数字初始化您的总和，并将其从列表中删除

d) 迭代：每当当前总和为正时，取最大的剩余负数并将其添加到总和中，并将其从列表中删除；每当当前总和为负数时，也一样。

通过这种方式，您有很大的机会（几乎）将精度损失降到最低，而这本来是不可避免的（考虑到数字的表示）。

于 2012-09-06T12:49:28.867 回答