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

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 类型的精度造成的。

到底哪种方法更好？哪种方法得出的数学平均值最接近实际值？

- jpo38

Answer 1

如果您真的需要高精度:

考虑使用任意精度算术（例如，使用GMP）

考虑使用Kahan求和算法（可能存在编译器问题）

考虑使用Shewchuk's-algorithm（在Python中可用作math.fsum） 编辑: math.fsum中的python文档也链接到this Overview of approaches。

- sascha

Answer 2

我的猜测是第一种方法可以得到更可靠的结果。在第二种情况下，每次迭代由于通过count进行的除法而进行一些近似计算，并最终将所有这些近似计算相加，从而导致您看到的结果差异。相反，在第一种情况下，只有在计算最终除法时才进行近似。

- lupod

---

不一定是真的。如果累加和在某个点非常接近下一个数的负数，添加数字列表可能会失去很多精度。 - rici

是的，但这也适用于第二类情况，如果av*count恰好接近-value。在这种特定情况下，我会选择第一类，因为它避免了每次添加新数字时进行除法运算。然而，我相信也有方法可以解决你提到的问题。 - lupod

是的，第二个算法也不好。经典的稳定算法是 newmean = oldmean + (newvalue - oldmean)/newcount。尽管它在每次迭代中都涉及除法，但比朴素的求和算法更稳定。（我相信它与Kahan求和算法大致相当。） - rici

Answer 3

约翰·D·库克进行了一项出色的分析，他建议：

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

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

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

最后是准确计算运行方差。

- Jacob

Answer 4

我的想法是两个计算方式都需要对大数值进行计算，然后再进行除法操作，这就解释了为什么您得到的结果是近似值。我会这样做：

class Average3
{
public:
    Average3() : av( 0 ), count( 0 ) {}

    void add( double value )
    {
        count++;
        av +=  (value - av)/count;
    }
...

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

- Diane M