97

Possible Duplicate:
Fastest way to determine if an integer's square root is an integer

What's a way to see if a number is a perfect square? 

bool IsPerfectSquare(long input)
{
   // TODO
}

I'm using C# but this is language agnostic.

Bonus points for clarity and simplicity (this isn't meant to be code-golf).

Edit: This got much more complex than I expected! It turns out the problems with double precision manifest themselves a couple ways. First, Math.Sqrt takes a double which can't precisely hold a long (thanks Jon).

Second, a double's precision will lose small values ( .000...00001) when you have a huge, near perfect square. e.g., my implementation failed this test for Math.Pow(10,18)+1 (mine reported true).

Improve this question
6
  • There was a very similar question. Please refer to stackoverflow.com/questions/295579/… for an excellent answer. Commented Dec 5, 2008 at 13:45
  • To the solution you choose, don't forget to prepend a quick check for negativeness. Commented Dec 5, 2008 at 13:51
  • Yes, I had that in there but removed it for brevity. Thanks for pointing it out though Commented Dec 5, 2008 at 13:53
  • You could also google for the 'lsqrt' method used for integer square root. Commented Dec 5, 2008 at 14:27
  • Michael, Bill the Lizard made a good point that it is just a similar question, not the exact duplicate. I don't think the question needs to be closed. Besides the problem of perfect square is much more complex in practical terms than it might seem and the answers here make some great contribution. Commented Dec 5, 2008 at 14:37

3 Answers 3

Reset to default
125 
bool IsPerfectSquare(long input)
{
    long closestRoot = (long) Math.Sqrt(input);
    return input == closestRoot * closestRoot;
}

This may get away from some of the problems of just checking "is the square root an integer" but possibly not all. You potentially need to get a little bit funkier:

bool IsPerfectSquare(long input)
{
    double root = Math.Sqrt(input);

    long rootBits = BitConverter.DoubleToInt64Bits(root);
    long lowerBound = (long) BitConverter.Int64BitsToDouble(rootBits-1);
    long upperBound = (long) BitConverter.Int64BitsToDouble(rootBits+1);

    for (long candidate = lowerBound; candidate <= upperBound; candidate++)
    {
         if (candidate * candidate == input)
         {
             return true;
         }
    }
    return false;
}

Icky, and unnecessary for anything other than really large values, but I think it should work...

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

Love the number of upvotes I got before correcting it to a more bulletproof solution ;)
dude, you're jon skeet.
@Jon: I'm thinking about rescinding my upvote. He asked for clarity and simplicity. :)
I assumed accuracy was important. Otherwise I'd have gone for the "guaranteed to be random" kind of response :)
You bulletproof solution is not needed. Tested exhaustively and sort-of proven.
|
12 
bool IsPerfectSquare(long input)
{
    long SquareRoot = (long) Math.Sqrt(input);
    return ((SquareRoot * SquareRoot) == input);
}
Improve this answer

Comments

9

In Common Lisp, I use the following:

(defun perfect-square-p (n)
  (= (expt (isqrt n) 2)
     n))
Improve this answer

3 Comments

Heh. Looking at stackoverflow.com/a/343862/31615, I should add that Common Lisp has a "complete" number stack, so this just works for any non-negative whole number (limited by working memory, of course).
On SBCL, square should be expt: (defun perfect-square-p (n) (= (expt (isqrt n) 2) n)).
@BenSima: Actually, since square is not defined in the standard, you need to define (or substitute) it in any implementation. I edit the answer in order not to have such a dependency.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.