 # Fastest way to determine if an integer's square root is an integer

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):

1. I’ve done it the easy way, by using the built-in `Math.sqrt()` function, but I’m wondering if there is a way to do it faster by restricting yourself to integer-only domain.
2. Maintaining a lookup table is impractical (since there are about 231.5 integers whose square is less than 263).

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

``````public final static boolean isPerfectSquare(long n)
{
if (n < 0)
return false;

long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}
``````

Note: I’m using this function in many Project Euler problems. So no one else will ever have to maintain this code. And this kind of micro-optimization could actually make a difference, since part of the challenge is to do every algorithm in less than a minute, and this function will need to be called millions of times in some problems.

I’ve tried the different solutions to the problem:

• After exhaustive testing, I found that adding `0.5` to the result of Math.sqrt() is not necessary, at least not on my machine.
• The fast inverse square root was faster, but it gave incorrect results for n >= 410881. However, as suggested by BobbyShaftoe, we can use the FISR hack for n < 410881.
• Newton’s method was a good bit slower than `Math.sqrt()` . This is probably because `Math.sqrt()` uses something similar to Newton’s Method, but implemented in the hardware so it’s much faster than in Java. Also, Newton’s Method still required use of doubles.
• A modified Newton’s method, which used a few tricks so that only integer math was involved, required some hacks to avoid overflow (I want this function to work with all positive 64-bit signed integers), and it was still slower than `Math.sqrt()` .
• Binary chop was even slower. This makes sense because the binary chop will on average require 16 passes to find the square root of a 64-bit number.
• According to John’s tests, using `or` statements is faster in C++ than using a `switch` , but in Java and C# there appears to be no difference between `or` and `switch` .
• I also tried making a lookup table (as a private static array of 64 boolean values). Then instead of either switch or `or` statement, I would just say `if(lookup[(int)(n&0x3F)]) { test } else return false;` . To my surprise, this was (just slightly) slower. This is because array bounds are checked in Java.
1 Like