Function to check for perfect square not working for large number

Question

I came across an algorithm to tell if a given number is perfect square or not in O(logN) time.

Here is the implementation(JAVA) of the idea.

public boolean isPerfectSquare(long x) {
        if (x <= 1)
            return true;
        
        long low = 1;
        long high = x;
        long mid = 0;
        while (low <= high) {
            mid = low + (high - low) / 2l;
            if (mid * mid == x)
                return true;
            else if (mid * mid < x)
                low = mid + 1;
            else
                high = mid - 1;
        }
        
        return false;
    }

This works fine for numbers like 256, 808201 , etc But fails for numbers like 999966000289.

I cannot figure out why?

Answer 1

As mentioned in the comments, the problem is that the intermediate mid*mid may overflow. It will help to use an unsigned type and a "long" or "long long" variant.

However, with the initial values of low and high, the first value of mid is close to x/4. If x is large, this is a great overshoot of the square root.

Hence, we can improve the range of manageable numbers by improving the initial low and high limit estimates.

Disclaimer: The Stack Overflow format is not suitable for long analysis. I have a good argument that the following works, part of which I have included below, but the full analysis is too lengthy to include here.

bool isPerfectSquare(unsigned long x) {
    if (x <= 1)
        return true;
        
    unsigned long low = 1;
    unsigned long high = x;

    // Improve the low/high limits
    while((low<<1) < (high>>1))
    {
        low <<= 1;
        high >>= 1;
    }

    unsigned long mid = 0;
    while (low <= high) {
        mid = low + (high - low) / 2l;
        if (mid * mid == x)
            return true;
        else if (mid * mid < x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return false;
}

With this modification, the initial value of mid is much smaller for large values of x and thus larger values of x can be handled without overflow.

It is not so difficult to show that the lower limit will not exceed the square root and doing that illustrates the intuition behind this method:

For some t, where 1<=t<2, x=t*2^r for some integer, r. Thus:

    sqrt(x) = sqrt(t) * 2^(r/2)

which implies that

    2^(r/2) <= sqrt(x) < 2^(r/2+1)

Thus a lower limit is a binary 1 shifted until it gets halfway (when r is even) or as close as possible (when r is odd) to the leftmost 1-bit in the binary representation of x. This is exactly what happens in the while-loop.

Showing that high is indeed an upper bound of the square root after the while-loop requires a longer analysis.