使用滑动平均法保持浮点数精度

Question

我需要计算任意数量数据点（至少100百万个）的16位操作的均方误差。 我决定使用滑动平均值，这样我就不必担心加上大量平方误差会导致溢出。 在100百万个样本时，我遇到了浮点精度问题（不准确的结果），因此我改用双精度浮点数。

这是我的代码：

int iDifference = getIdeal() - getValue();

m_iCycles++;


// calculate the running MSE as

// http://en.wikipedia.org/wiki/Moving_average

// MSE(i + 1) = MSE(i) + (E^2 - MSE(i))/(i + 1)

m_dMSE = m_dMSE + ((pow((double)iDifference,2) - m_dMSE) / (double)m_iCycles);

有没有更好的方法来实现这个以保持准确性？我考虑将MSE归一化为1，然后仅保留一个总和，在完成时进行最终除法以计算平均值。

- Jason George

---

作为完全的旁注，取决于您选择使用pow(double, int)重载，iDifference*iDifference可能比pow调用快几个数量级。 - Mark B

同意。我应该注意到那个的。谢谢马克！ - Jason George

Answer 1

你可能需要查看Kahan求和算法 - 它与你在这里所需的不完全相同，但它解决了一个非常类似的问题，你可以尝试根据自己的需求进行调整。

- Paul R

---

非常酷，+1。然而，一旦运行总数足够大，添加任何误差实际上都会添加0，那么这种方法就不再有效了。此时，误差累加器开始迅速增长，直到失去精度。然后他又回到原点。 - Potatoswatter

+1，绝对很酷。我倾向于同意Potatoswatter的观点，随着数据点数量的增加，我仍然会失去精度。 - Jason George

Answer 2

浮点数在这种情况下不会溢出，而只会失去精度。因此，在这里运行平均值和运行总数之间没有优势。无论是运行总数还是分母增长，后果都是相同的。

为了保持运行总数的精度，请保留子总数而不是单个总数。只需将其添加到子总数中，直到再添加一个子总数会导致溢出为止。然后转移到下一个子总数。由于它们在2进制下的数量级相同，可以通过转换为浮点数并将其成对累加到一个最终总数中来达到最佳精度。

// first = errors, second = counter
typedef pair< vector< uint32_t >, uint32_t > running_subtotals;

void accumulate_error( uint32_t error, running_subtotals &acc ) {
    ( numeric_limits< uint32_t >::max() - error < acc.first.back()?
        * acc.first.insert( acc.first.end(), 0 ) : acc.first.back() )
        += error; // add error to current subtotal, or new one if needed
    ++ acc.second; // increment counter
}

double get_average_error( running_subtotals const &total ) {
    vector< double > acc( total.first.begin(), total.first.end() );
    while ( acc.size() != 1 ) {
        if ( acc.size() % 2 ) acc.push_back( 0 );
        for ( size_t index = 0; index < acc.size() / 2; ++ index ) {
            acc[ index ] = acc[ index * 2 ] + acc[ index * 2 + 1 ];
        }
        acc.resize( acc.size() / 2 );
    }
    return acc.front() / total.second;
}

- Potatoswatter

---

浮点数在这种情况下不会溢出，只会丢失精度。但是，丢失精度会导致溢出吗？一个精度较低的浮点数可能比实际值更小或更大，不是吗？ - Joseph Garvin

@JosephGarvin 当加数的最高有效位小于总和的最低有效位时，向下舍入是有保证的。否则，你是对的，四舍五入的目的是防止这种偏差。(完全消除偏差需要线性分布的数字，但许多数据集具有指数或其他不均匀的分布。) 一个设计良好的程序应该永远不会接近溢出(到无穷大); 我认为在误差范围内有INFINITY将是一个错误。 - Potatoswatter

Answer 3

如果您的其他解决方案无法解决问题，可以考虑使用“大数”库（Bignum library）。

“GMP是一个免费的库，用于任意精度算术运算，可操作有符号整数、有理数和浮点数。除了机器可用内存所暗示的限制外，没有实际精度限制。GMP具有丰富的功能，并且这些功能具有规律的接口。”

- Jay

---

我也很喜欢这个。最终决定不为单个变量添加任何额外的开销。 - Jason George