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

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)
• 考虑Kahan求和算法 (可能的编译器问题)
• 考虑一下Shewchuk算法 (它在Python math.fsum中可用)

编辑：，math.fsum中的python也链接到1.本办法概述

Answer 2

我猜第一堂课会给出更可靠的结果。在第二种情况下，在每次迭代时，由于计数除法，您可以进行一些近似，最后，所有这些近似都会导致所看到的结果的差异。在第一种情况下，您只是在计算最后的除法时进行近似。

Answer 3

约翰·D·库克(JohnD.Cook)给出了一个很好的分析，他建议：

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

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

然后是数值结果的理论解释

最后一次精确计算运行方差