整数乘法和除法之间意外的性能差异

我正在实现一个简单的二分查找来查找整数的平方根。代码正确运行。但是，如果我将if中的条件从mid * mid > x更改为mid > (x/mid)，则似乎超时了大输入，则一切正常。整数乘法和除法之间意外的性能差异

int sqrt(int x) { 
    if(x < 0) return -1; 
    if(x <= 1) return x; 
    int l,r,mid,ans; 
    l = 0; 
    r = x; 
    while(l <=r){ 
     mid = (l + r)/2; 

     if((mid * mid) == x) return mid; 

     if((mid * mid) > x){ //<===== here if I change to mid > (x/mid) 
      r = mid - 1; 

     }else{ 
      l = mid + 1; 
      ans = mid; 
     } 
    } 

    return ans; 
}

};

因此我得出结论，划分比乘法更快。但是迄今为止我所做的研究都指向乘法比分裂更快。

来源

2014-04-09 Leo

的[I应该使用乘法或除法？]可能重复（http://stackoverflow.com/questions/226465/should-i-use-multiplication-or-division） – sashoalm

我具有重复不同意，因为这是更加关于浮点算术，而这种情况是整数算术。我也编辑过这个标题。 OP，如果您不同意，请回滚。 – Bathsheba

你在不到一分钟内就投了票，你真的看过我的问题吗？ – Leo

mid > (x/mid)

优于

(mid * mid) > x

，因为你避免整数溢出。

来源

2014-04-09 07:59:05 UmNyobe

非常感谢，我很傻，没有想到，错误总是说“时间限制超过”，我只是不断思考速度。 – Leo

没问题。你和编写代码的人一样愚蠢。 – UmNyobe

大输入的问题是mid * mid > x可能溢出整数，然后二进制可能会进入一个非常奇怪的状态。在这种情况下，你也许会得到正确的值，但这是纯粹的运气。另一方面，使用除法可避免整数溢出。

来源

2014-04-09 07:59:49

非常感谢您的回答，我只能接受一个答案。既然你有更多的声望，我会接受其他人:) – Leo

整数乘法和除法之间意外的性能差异

回答

相关问题