Mobile Technologies
Web Technologies
Digital Marketing
Creative Design
Career Talk
Medical
General Tech
Interviews
Internet Of Things

Embark on a journey of knowledge! Take the quiz and earn valuable credits.

Take A QuizChallenge yourself and boost your learning! Start the quiz now to earn credits.

Take A QuizUnlock your potential! Begin the quiz, answer questions, and accumulate credits along the way.

Take A QuizMobile Technologies Mobile Computing . 1 year ago

_x000D_
_x000D_
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'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.
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.

Turn Your Knowledge into Earnings.

Mobile Technologies 1 Answers

Mobile Technologies 0 Answers

Mobile Technologies 0 Answers

Mobile Technologies 0 Answers

Banking, Finance & Insurance

Mobile Technologies

Career Talk

General Tech

Commerce & Accounting

Internet of Things0 Answers

Commerce & Accounting0 Answers

Internet of Things0 Answers

Medical0 Answers

Management0 Answers

Ask Anything

Hello! How can I assist you today?

Whether you have questions, need information, or just want to chat, feel free to let me know

Your experience on this site will be improved by allowing cookies.