Friday, May 2, 2014

Finding the integer square root of a number

How do we implement a function to find the integer square root of a number?

For example int_sqrt(4) = 2, int_sqrt(10) = 3. (We have to take floor of the actual square root)

A simple method is to iterate i from 1 to N/2 and keep checking until i2 < N, and whenever i2 >= N return i.

for( int i = 1; i <= N/2 ; i++ )
    if( i*i >= N )
        return i;

But this algorithm takes O(n) time. For large numbers this takes a lot of time. Any way to improve this further?

Binary search comes to our rescue. we start with the initial range [0, N]. In each iteration we check if mid2 <= N and (mid+1)2 >N. If this is satisfied, we return mid.

If mid2 > N, we confine our search to the left half; otherwise we search in the right half.

This implementation takes only O(log N) time.

Here is the C++ implementation.