What's the Fastest Way to Determine if the Square Root of an Integer is an Integer?

The fastest way to determine whether the square root of an integer is an integer

Problem Description

I am looking for the fastest way Method to determine whether a long integer is a perfect square (i.e. its square root is another integer):

1. I did it using the built-in Math.sqrt() function, but I'm curious if there is a way to do it using integer fields , thereby increasing the speed.


2. It is impractical to maintain a lookup table (since there are approximately 2^31.5 integers whose squares are less than 2⁶³).

Here is the very simple and straightforward way I do it now:

{<br> if (n < 0)</p><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">return false;

Copy after login

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

_{Note: I use this function in many Project Euler problems. Therefore, there will not be any maintenance on this code in the future. And this micro-optimization can actually make a difference, because part of the challenge is taking less than a minute to complete each algorithm, whereas this function needs to be called millions of times in some problems.}

---

I have tried different solutions to this problem:

• After exhaustive testing, I found that adding 0.5 to the result of Math.sqrt() is unnecessary, at least on my machine.


• Fast inverse square root is faster than Math.sqrt() but gives incorrect results for n >= 410881. However, as BobbyShaftoe suggested, we can use the FISR hack for n
• Newton's method is much slower than Math.sqrt(). This is probably because Math.sqrt() uses something similar to Newton's method, but is implemented in hardware and therefore much faster than in Java. Additionally, the Newton method still requires the use of double-precision floating point numbers.
positive 64-bit signed integer), and it is slower than Math.sqrt().

• Binary search is even slower. This makes sense, since a binary search requires an average of 16 passes to find the square root of a 64-bit number.


• According to John's testing, using an or statement is faster than using a switch in C, but in Java and C# there seems to be no difference between an or and a switch.


• I also tried making a lookup table (as a private static array of 64 booleans). Then, instead of using a switch or or statement, I would just say if(lookup[(int)(n&0x3F)]) { test } else return false;. To my surprise, this is (slightly) slower. This is because array bounds are checked in Java.

The above is the detailed content of What's the Fastest Way to Determine if the Square Root of an Integer is an Integer?. For more information, please follow other related articles on the PHP Chinese website!