C++小浮点数之和

Question

假设我们有一个包含小数（约为10^(-15)）的双精度数数组c++。如果我们按顺序计算该数组中数字的总和，例如：

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

我们得到了一些值x。

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

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

- Nurlan

---

是的，你可以，但需要将它们转换为形式a/b。否则，你就不能这样做。但一般来说，你不能这样做，因为在C++语言中没有内置这个功能。事实上，你真的不行，因为0.66666666不能转化为有理数。也许Boost库可以帮助你。当你说“不失精度”时，意味着你不会遭受太大影响（你需要一定程度的期望）。 - CppLearner

你如何知道在两种方法中，哪一种失去了更多的准确性？ - juanchopanza

通过将结果写入文件来实现。例如：1.9999920040000227000000000与1.9999920040000230000000000或0.0000000118158038744022090与0.0000000118158038365459910。 - Nurlan

如果它们都差不多小，那么它们的小差异对结果的准确性没有影响。如果你将它们全部乘以2^50，相加，然后将结果除以2^50，你将得到完全相同的结果。 - TonyK

Answer 1

使用Kahan求和算法：

通过Kahan求和算法：

#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

在这里查看代码。

- Peter Wood

---

仅仅是说，这个例子并没有真正证明任何东西，因为你可以用普通的求和得到相同的结果。我自2014年以来就没有在C++上工作过了，也没有时间去改进它，但是欢迎提出建议/编辑。 - Peter Wood

Answer 2

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

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

但是，如果您真正意味着不失去任何精度，那么您的结果不一定适合于double。如果这确实是您想要的，请查看Algorithm 908 http://dl.acm.org/citation.cfm?id=1824815或类似算法。

- George

Answer 3

在这种情况下的诀窍是先将数组从小到大排序，然后在您制定的循环中对它们进行求和。这样，精度最好。

您还可以查看Kahan求和算法。

- Jorge Leitao

---

Kahan算法是最通用的，但如果值都差不多，递归地将数组分成两半并求和每一半将提供明显更好的精度。 - James Kanze

Answer 4

考虑使用卡汉求和算法来处理整个数据集或每个子集。

还有其他问题涉及到此算法，可以帮助您。

- Zeugma

Answer 5

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

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

- Ivaylo Strandjev

Answer 6

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

- Martin James

Answer 7

可能是因为您的个别求和在80位寄存器中被优化和执行，但随后转换回64位双精度浮点数（请阅读有关编译器开关的内容）。自然地，这会丢失精度。如果是这种情况，则将数组分解并添加各个64位求和将与将它们全部作为80位加和并将总和转换回来得到不同的答案。

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

- Component 10

---

我认为这并不是真正的问题。问题在于随着他在表中前进，总和的大小相对于单个值的大小变得很大，而添加不同大小的值会失去很多精度。 - James Kanze

我说过这可能是问题所在。我同意，加上不同数量级的数字可能会失去精度，但他是否在暗示它们都很小（约为10^(-15)），而他的问题不是将它们全部加在一起会失去精度，而是将它们一次性全部加在一起比分批求和再将批次总和相加得到的答案更精确？ - Component 10

他的数组中所有的值都有相似的数量级。然而，在添加了前几百个之后，他要加的总和明显具有更大的数量级。批量求和的解决方案可能更精确，因为数量级的差异将会更小。 - James Kanze

Answer 8

在处理非常小的数字时，加法运算结果的精度损失与处理正常大小的数字时并没有什么不同。可能相关的是： a）数字之间的相对大小差异是否很大？ b）这些数字是否有不同的符号？

最后一个问题通常涉及到加法精度。 你应该做的-也许不完全是最优的，但是一个公平的尝试，并且易于实现-是：

a）将它们分成正数和负数的子集

b）对每个子集进行排序

然后

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

d）迭代地：每当当前总和为正数时，取剩余负数中最大的一个并将其添加到总和中，并将其从列表中删除；每当当前总和为负数时，执行类似操作。

通过这种方式，您有一个公平的机会（几乎）将精度损失最小化到本质上无法避免的程度（考虑到数字的表示方式）。

- Bert te Velde