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

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-docs也链接到此方法概述