2
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ n can be big number let's say than what we can do to improve this? can you update your answer with binary search suggestion so that I can understand better? \$\endgroup\$ – user5447339 Oct 4 '18 at 23:27
  • \$\begingroup\$ @user5447339 As I said, binary search. See edit. \$\endgroup\$ – vnp Oct 4 '18 at 23:35
  • \$\begingroup\$ "if inside a tight loop usually hurts performance." - is that explained in this infamous SO answer about branch prediction? \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Oct 4 '18 at 23:57
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ I am not sure the branch prediction is applicable to bytecode (it is java after all). Just count the instructions. Emphasis on tight. \$\endgroup\$ – vnp Oct 5 '18 at 0:07
1
\$\begingroup\$

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*4k we can get rid of the 4k part since either n is a square and its square root is n*2k or it isn't and that must mean m is not a square because the 4k 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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.