高精度计算平均值的最佳策略

Question

我比较了两种计算随机数平均值的算法。

• 第一个算法将所有数字相加并除以最后的项目计数
• 第二种算法计算每次迭代的平均值，并在收到新数据时重用结果

我想这里没有什么革命性的，而且我不是数学家，所以我不能给这两种算法命名。

这是我的代码：

#include <iostream>
#include <iomanip>
#include <cstdlib>
class Average1
{
public:
    Average1() : total( 0 ), count( 0 ) {}
    void add( double value )
    {
        total += value;
        count++;
    }
    double average()
    {
        return total/count;
    }
private:
    double total;
    size_t count;
};
class Average2
{
public:
    Average2() : av( 0 ), count( 0 ) {}
    void add( double value )
    {
        av = (av*count + value)/(count+1);
        count++;
    }
    double average()
    {
        return av;
    }
private:
    double av;
    size_t count;
};
void compare()
{
    Average1 av1;
    Average2 av2;
    double temp;
    for ( size_t i = 0; i != 100000000; ++i )
    {
        temp = static_cast<double>(std::rand()) / static_cast<double>(RAND_MAX);
        av1.add( temp );
        av2.add( temp );
    }
    std::cout << std::setprecision(20) << av1.average() << std::endl;
    std::cout << std::setprecision(20) << av2.average() << std::endl;
}
int main()
{
    compare();
    return 0;
}

输出为：

0.50001084285722707801
0.50001084285744978875

差异肯定是由于double型精度。

最后，哪一个是好方法？哪一个给出了真正的数学平均值（或最接近...）？

Answer 1

如果你真的想要高精度：

• 考虑任意精度算术（例如使用 GMP）
• 考虑卡汉求和算法 （可能的编译器问题）
• 考虑Shewchuk的算法（在Python中以math.fsum的形式提供）

编辑：math.fsum 中的 python-docs 也链接到此方法概述

Answer 2

我的猜测是，第一个类给出了更可靠的结果。在第二种情况下，在每次迭代中，由于除以计数，您会进行一些近似运算，最终所有这些近似值加起来就是您看到的结果差异。相反，在第一种情况下，您只需在计算最终除法时进行近似值。

Answer 3

John D. Cook给出了一个很好的分析，他推荐：

av = av + (value - av)/count;

他的帖子从比较三种计算标准偏差的方法开始。

然后数值结果的理论解释

最后 准确计算运行方差

Answer 4

我自己的想法是，在除以之前，两者都计算计数乘以值，这是一个很大的数字，这解释了为什么你的结果是近似的。我会做的：

class Average3
{
public:
    Average3() : av( 0 ), count( 0 ) {}
    void add( double value )
    {
        count++;
        av +=  (value - av)/count;
    }
...

但是在添加最后一个数字时仍然会失去精度，因为与平均值相比，添加值/计数很小。我很高兴知道我的直觉是否正确