有限空间平均计算

Question

假设我有N个整数，其中N可以变得很大，但每个int都保证在0和某个上限M之间，其中M很容易适合有符号的32位字段。

如果我想计算这N个整数的平均值，我不能总是在有符号的32位空间中对它们求和除以-如果N太大，分子就有溢出的风险。这个问题的一种解决方案是只使用64位字段进行计算，以容纳更大的N，但这种解决方案不具有伸缩性-如果M是一个大的64位整数，同样的问题也会出现。

有没有人知道一种算法(最好是O(N))可以计算同一比特空间中正整数列表的平均值？不需要做一些便宜的事情，比如用两个整数来模拟一个更大的整数。

Answer 1

假设您最初知道M，您可以保留两个变量，一个是到目前为止的答案除以M，另一个是余数。

例如，在C++中：

int ans = 0, remainder = 0;
for (int i=0;i<N;i++) {
  remainder += input[i]; // update remainder so far
  ans += remainder/N; // move what we can from remainder into ans
  remainder%=N; // calculate what's left of remainder
}

在循环结束时，答案在ans中找到，余数在remainder中找到(如果需要舍入方法而不是截断)。

此示例适用于最大输入数M+N适合32位整数的情况。

注意，这应该适用于正整数和负整数，因为在C++中，/运算符是除法运算符，而%实际上是余数运算符(不是真正的模运算符)。

Answer 2

你可以计算一个移动平均值。如果您有N元素的平均A，并且添加了另一个元素E，则新的平均值为(A*N+E)/(N+1)。根据除法对加法的分配特性，这等同于(A*N)/(N+1) + E/(N+1)。但是如果A*N溢出，您可以使用乘法和除法的关联属性，您可以将第一项转换为A*(N/N+1)。

所以算法是：

n = 0
avg = 0
for each i in list
  avg = avg*(n/(n+1)) + i/(n+1)
  n = n+1