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

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 summation algorithm (可能的编译器问题)
• 考虑Shewchuk's-algorithm (在 Python 中可用 math.fsum )

编辑: math.fsum 中的 python 文档也链接到 this Overview of approaches