整數乘法和除法之間意外的性能差異

我正在實現一個簡單的二分查找來查找整數的平方根。代碼正確運行。但是，如果我將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

整數乘法和除法之間意外的性能差異

回答

相關問題