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

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.