实现数学公式时溢出问题(Overflow issues when implementing math

听说，计算平均值时，开始+（端开始）从/ 2的不同（起始+端）/ 2，因为后者会引起溢流。我不明白为什么这第二个可能导致溢出而第一个没有。什么是实现一个数学公式，可避免溢出的通用规则。

Answer 1:

假设其中最大整数值为10，你要计算的5和7的平均使用的是一台电脑。

第一种方法（开始+（端开始）/ 2），得到

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

第二种方法（开始+端）/ 2给出了一个溢流，由于中间12值是在10我们接受的最大值和“换行之上”到别的东西（如果使用的是无符号数其通常包回零，但如果你的号码被签署，你可以得到一个负数！）。

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

当然，在实际应用的计算机在如2 ^ 32，而不是10一大的值的整数溢出，但这个想法是一样的。不幸的是，没有“一般”的方式来摆脱溢出，我知道的，这在很大程度上取决于你使用的特定算法。而事件的话，事情变得更加复杂。您可以根据您的引擎盖下使用的号码类型得到不同的行为，还有其他类型的数值误差的担心，除了过度和下溢。

Answer 2:

无论您的公式将溢出，但根据不同的情况：

的(start+end)的一部分(start+end)/2时的式会溢出start和end都接近整数限制在范围（即正或负二者）的同一侧。
的(end-start)你的一部分start+(end-start)/2式时将溢出start为正， end是负的，并且这两个值接近可表示的整数值的相应端部。

有没有“通用”的规则，你做的情况下，逐案：看您的公式的一部分，认为这可能导致溢出的情况，并想出了各种办法来避免它。例如， start+(end-start)/2可以示出的公式来避免上溢时，用相同的符号的平均值。

这是艰辛的道路; 最简单的方法是使用高容量的表示，中间结果。例如，如果你用long long ，而不是int做中间计算和结果复制回int ，当你完成而已，你会避免溢出假设最终结果在适合int 。

Answer 3:

当与整数处理，你可能关心的整数溢出采用这种策略的时候。

注意，使用公式b+(ba)/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

我莫名其妙地感到有一个你上述公式的关系...

Answer 4:

在二进制搜索，我们会写代码如下：

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

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

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

文章来源: Overflow issues when implementing math formulas