What's a good algorithm to determine if an input is a perfect square?

Question

Closed as Exact 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).

Answer 1

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

Answer 2

bool IsPerfectSquare(long input)
{
    long SquareRoot = (long) Math.Sqrt(input);
    return ((SquareRoot * SquareRoot) == input);
}

Answer 3

There was a very similar question. Please refer to http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer for an excellent answer.

Answer 4

In Common Lisp, I use the following:

(defun perfect-square-p (n)
  (= (square (isqrt n))
     n))

Answer 5

To the solution you choose, don't forget to prepend a quick check for negativeness.