65.9K
CodeProject 正在变化。 阅读更多。
Home

大整数数组平均值的精确且安全计算方法

Stefan_Lang
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.91/5 (11投票s)

2014年8月13日

CPOL

4分钟阅读

viewsIcon

28085

如何避免溢出并在进行大整数计算时保持精度。

引言

整数计算，如果过度进行，可能会很棘手。即使数值在正常范围内，重复的加法和其他运算也可能导致整数溢出。当这个问题出现时，即使是最简单的算法也可能难以实现。

通常的解决方案是使用更高精度的数be型（如 long long 或 double）来执行中间值的计算。

本文提供了一种替代算法，用于计算大量整数值的平均值，其前提是计算需要精确，因此不能使用 double 作为中间值的be型。该算法源于此处提出的一个问题：https://codeproject.org.cn/Messages/4878957/Calculute-average-value-of-large-array.aspx。

背景

该线程中用户 k5054 发布的一个链接指向了累积移动平均（Cumulative Moving Average）方法：http://en.wikipedia.org/wiki/Moving_average#Cumulative_moving_average。该方法提供了一种计算一系列数字平均值的替代方法。虽然该方法并不关注整数溢出问题，但它提供了一种逐步确定系列部分平均值的方法，从而无需使用可能发生溢出的、值较大的中间be型。

改进算法

该算法逐步计算到当前点为止所有值 xi 的累积移动平均值（CMA）。为了避免每次迭代都需要重新访问先前的值，该计算使用了基于前一个平均值的替代公式。

CMAn+1 = CMAn + (xn+1 - CMAn) / (n+1)

在此方程中，所有值和中间结果的量级与原始值相同。你能获得的最大的中间值是输入值中的最大值与最小值之差：例如，如果这两个值分别存储在 x1 和 x2 中，那么上述公式将在第二次迭代中计算出 x2 - x1 之差。

然而，此公式假设进行精确计算：如果第二项的除法是整数除法，则会舍去一些小数部分，而这些小数部分累积起来可能达到相当大的值。因此，我们需要跟踪除法的累积余数（CMR）。

CMAn+1 = CMAn + (xn+1 - CMAn + CMRn) div (n+1)

CMRn+1 = (xn+1 - CMAn + CMRn) mod (n+1)

这里最大的中间值是两个公式中使用的除数 (xn+1 - CMAn + CMRn)。减法最多会产生 xi 的最小值和最大值之间的差值，而 CMR 的值可以在 -n 到 n 之间（如果除数为负数，余数也可能为负）。因此，只要输入值的范围不占据整数范围的大部分，或者元素的数量接近所用整数类型的最大整数值，就不会发生溢出。

使用代码

该代码使用了 C++11 的特性 decltype 和 std::remove_reference。我在 VS2010 中实现了并测试了它。请注意，我特意没有为 n_values 使用 size 类型，即使它不可能是负数。原因是除法和取模运算符对混合符号/无符号参数不总是提供预期的结果。此外，为了避免溢出，n_values 必须在基本be型范围内。

#include <utility>

template <class container_iterator>
auto average(const container_iterator start, container_iterator end)
   -> typename std::remove_reference<decltype(*start)>::type
{
   typedef std::remove_reference<decltype(*start)>::type basetype;

   basetype cumulated_average = 0;
   basetype cumulated_remainder = 0;
   basetype addendum = 0;
   basetype n_values = 0;
   for (auto pvalue = start; pvalue != end; ++pvalue) {
      ++n_values;
      addendum = *pvalue - cumulated_average + cumulated_remainder;
      cumulated_average += addendum / n_values;
      cumulated_remainder = addendum % n_values;
   }
   return cumulated_average;
}

该代码提供了一个单一函数，其用法类似于 STL 库中的许多算法。它接受两个参数，这两个参数定义了容器中值的范围。该函数将自动从这些参数推导出容器内值的be型。如果您的编译器不支持 C++11 的 decltype 和 std::remove_reference 特性，则可以将值be型作为模板参数列表中的一个参数来添加。

您可以通过简单地传递指向容器中第一个元素和最后一个元素之后（不包含）的迭代器或指针来调用此函数，以计算平均值。这是一个例子。

void test_average() {
   char cvalues[] = { 13,7,-27, 34, -3, 22, 33, -1, 18, 29,
                      13,7,-27, 34, -3, 22, 33, -1, 18, 29,
                      13,7,-27, 34, -3, 22, 33, -1, 18, 29,
                      13,7,-27, 34, -3, 22, 33, -1, 18, 29,
                      13,7,-27, 34, -3, 22, 33, -1, 18, 29
                    };
   auto cavg = average(cvalues, cvalues+50);
}

在调试此示例时，我发现值的范围是：

  • cvalues: -27 到 +34
  • cumulated_remainder: -28 到 +25
  • cumulated_average: -2 到 +13

所有值都在预测范围内。这只是一个测试用例，但原始代码确实包含了更多的调试代码，这些代码有助于断言 cumulated_average 和 cumulated_remainder 的值在所有时间点都是准确的。

关注点

这是我第一次真正使用 decltype，并且在尝试弄清楚如何正确使用它时，是我第一次听说 std::remove_reference。这些新的语言特性非常有用，如果您还没有阅读过，那么值得花时间了解一下。在此示例中，使用它们为我节省了一个模板参数。但更重要的是，它为调用者节省了提供该参数的精力，也为我节省了验证传递给函数的迭代器是否确实指向完全相同be型值的精力。

我还想指出，统计学中还有其他一些相关的算法也存在迭代形式，例如计算标准差。然而，我无法想象为什么有人会愿意在这些方面限制自己使用整数算术。但当您面临大量数据时，迭代公式仍然可能很有用。

历史

2014-08-13 文章初稿

© . All rights reserved.