Fastest way to determine if a number is perfect square

Question

I'm looking for the fastest way to determine if a long value is a perfect square (i.e. its square root is another integer). I was asked this in an interview recently.

Here is the very simple and straightforward way I'm doing it now:

  private static boolean isSquare(long n) {
    int i = 1;
    for (;;) {
      if (n < 0)
        return false;
      if (n == 0)
        return true;
      n -= i;
      i += 2;
    }
  }

Is there any better way by which we can do this or optimize this more?

Answer 1

It is indeed very simple and straightforward. The time complexity is however \$(O(\sqrt n)\$. A binary search variation will do it in \$O(\log n)\$ time. Along the lines of the pseudocode:

    while lo < hi
        mid = lo + (hi - lo)/2
        square = mid * mid
        if square == n
            return true
        if square < mid
            lo = mid
        else
            hi = mid
    return false

Depending on the expected magnitude of \$n\$ it may or may not worth the effort. In the interview setting (no restrictions on \$n\$) I would go for the binary search.

---

if inside a tight loop usually hurts performance. Consider

    while (n > 0) {
        n -= i;
        i += 2;
    }
    return n == 0;

Answer 2

There are some really quick filters that you can run before the "main test" that quickly detect a large number of non-squares, and some quick "reductions" that make the number smaller while ensuring that its "squareness" property does not change (this is useful since here the square root itself is not needed, we only need to know whether it exists).

For example, given a number n=m*4^k we can get rid of the 4^k part since either n is a square and its square root is n*2^k or it isn't and that must mean m is not a square because the 4^k part cannot cause non-square-ness.

So, the powers of 4 can be divided out, for example:

n >>= Long.numberOfTrailingZeros(n) & -2;

The & -2 rounds down the number of trailing zeros to an even number, so the shift only removes powers of 4.

Then, with the pre-condition that x is odd (if the powers of 4 are removed from n then the powers of 2 are removed from its square root .. unless n = 0 but you can add if (n == 0) return true;) there are much fewer than 8 possible outcomes for (x * x) % 8, namely only 1: 1. That gives a really efficient filter:

if ((n & 7) != 1)
    return false;

This combination of tricks can be prepended to any "perfect square test" in order to run the main test only about 1/8th of the time assuming uniform random input, so together they can be used to make anything faster unless it is expected that most inputs are actually squares.

Answer 3

Is there a reason you are dismissing the obvious solution?

 public static boolean naive_test_square(long n) {
     long sr = (long) Math.sqrt(n);
     return sr*sr == b;
 }

Which is 7x faster than your solution in my tests.