4

我听说，在计算平均值时，start+(end-start)/2 与 (start+end)/2 不同，因为后者会导致溢出。我不太明白为什么第二个会导致溢出，而​​第一个不会。实现可以避免溢出的数学公式的通用规则是什么。

4

4 回答 4

12

假设您使用的计算机的最大整数值为 10，并且您想要计算 5 和 7 的平均值。

第一种方法 (begin + (end-begin)/2) 给出

5 + (7-5)/2 == 5 + 2/2 == 6

第二种方法 (begin + end)/2 给出了溢出，因为中间的 12 值超过了我们接受的最大值 10 并“换行”到其他东西（如果您使用无符号数字，通常会换行到零，但如果你的数字是签名的，你可能会得到一个负数！）。

12/2 => overflow occurs => 2/2 == 1

当然，在实际计算机中，整数会以 2^32 而不是 10 这样的大值溢出，但想法是一样的。不幸的是，没有我所知道的摆脱溢出的“通用”方法，这在很大程度上取决于您使用的特定算法。然后事件，事情变得更加复杂。根据您在后台使用的数字类型，您可以获得不同的行为，除了上溢和下溢之外，还有其他类型的数字错误需要担心。

于 2012-06-04T13:48:51.243 回答
5

您的两个公式都会溢出，但在不同的情况下：

  • 当并且都接近范围同一侧的整数限制时（即均为正数或均为负数）(start+end)，您的(start+end)/2公式部分将溢出。startend
  • 当为正数和负数时，公式的(end-start)一部分将溢出，并且两个值都接近可表示整数值的各自末端。start+(end-start)/2startend

没有“通用”规则，您可以根据具体情况进行操作：查看公式的某些部分，考虑可能导致溢出的情况，并想出避免溢出的方法。例如，start+(end-start)/2当您对具有相同符号的值进行平均时，可以显示公式以避免溢出。

这是艰难的道路；简单的方法是对中间结果使用更高容量的表示。例如，如果您使用long long而不是int进行中间计算并仅在完成后将结果复制回，int则假设最终结果适合int.

于 2012-06-04T13:57:16.623 回答
1

在处理整数时，您可能会在采用此类策略时关心整数溢出。

请注意，使用公式b+(b-a)/2您要确保a <= b. 否则，您可能会在可能值范围的下限处遇到相同的问题。想想a/2+b/2。然而，这种方法也有其他缺点。

处理浮点数时会出现另一个问题，即灾难性取消。由于浮点表示的有效数字数量有限，当添加大量数字时，准确性会丢失（即使这只是一个中间步骤）。

为了解决这个数值稳定性问题，例如可以使用这个算法（稍微改编自维基百科）：

def online_mean(data):
  n = 0
  mean = 0

  for x in data:
    n = n + 1
    delta = x - mean
    mean = mean + delta/n

  return mean

我不知何故觉得与你上面提出的公式有关系......

于 2012-06-04T13:58:42.253 回答
0

在二分搜索中，我们将编写以下代码：

if(start > end){
   return;
}
int mid = start + (end - start) / 2;

通过使用start + (end - start) / 2，我们可以避免@dasblinkenlight 指出的问题

如果我们使用(start + end) / 2，它会溢出，如 dasblinkenlight 所示

于 2013-08-19T06:00:58.080 回答