2

I am implementing a simple binary search to find the square root of a integer. The code runs correctly. But it seems to timeout for large inputs if I change the condition in the if from mid * mid > x to mid > (x / mid) then all is fine.

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;
}

};

Therefore I conclude that division is faster than multiplication. But the research I've done so far all points to multiplication being faster than division.

Bathsheba
  • 231,907
  • 34
  • 361
  • 483
Leo
  • 335
  • 2
  • 11
  • possible duplicate of [Should I use multiplication or division?](http://stackoverflow.com/questions/226465/should-i-use-multiplication-or-division) – sashoalm Apr 09 '14 at 07:58
  • 2
    I disagree with the duplicate as that is more about floating point arithmetic whereas this case is integer arithmetic. I've also edited the title to reflect this. OP, please rollback if you disagree. – Bathsheba Apr 09 '14 at 08:00
  • You down voted in less than one minutes, did you really read my question ? – Leo Apr 09 '14 at 08:00
  • @Bathsheba: Yes I agree, I was worried nobody gonna answer my question because of the down vote, thank you. – Leo Apr 09 '14 at 08:05
  • I edited it in the end. The two answers (at the time of my writing) are correct. – Bathsheba Apr 09 '14 at 08:15
  • @Bathsheba Thanks I was editing too, but your English more concise. – Leo Apr 09 '14 at 08:17

2 Answers2

3
mid > (x / mid)

is better than 

(mid * mid) > x

because you avoid integer overflow.

UmNyobe
  • 22,539
  • 9
  • 61
  • 90
  • Thanks very much, I am so silly,did not think of that, the error keep saying "Time Limit Exceeded", I just keep thinking about speed. – Leo Apr 09 '14 at 08:07
3

The problem for the big input is that mid * mid > x may overflow integer and then the binary may enter a very strange state. Also you may be getting correct values in that case but this is somewhat pure luck. On the other hand, using division avoids integer overflow.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • Thanks very much for the answer, I can only accept one answer. Since you have much more reputation, I will accept the other guy :) – Leo Apr 09 '14 at 08:19