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

Question

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

Alecalecia

There was a very similar question. Please refer to #296079 for an excellent answer. – Maudmaude

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

Yes, I had that in there but removed it for brevity. Thanks for pointing it out though – Alecalecia

You could also google for the 'lsqrt' method used for integer square root. – Highlander

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

I don't know how fast the method can tell if an integer is a square. This method does not use the square root or Newton's method. It can be found here: math.stackexchange.com/questions/4226869/… – Senatorial

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

Flu

Looks as if you were faster than me ;-) Oops - your solution is also better, because 'closestRoot' is a far mor accurate name. – Anabelle

Love the number of upvotes I got before correcting it to a more bulletproof solution ;) – Flu

dude, you're jon skeet. – Procopius

@Jon: I'm thinking about rescinding my upvote. He asked for clarity and simplicity. :) – Bioplasm

I assumed accuracy was important. Otherwise I'd have gone for the "guaranteed to be random" kind of response :) – Flu

What's an example input that fails with your first method? – Alecalecia

Ah, I get it now. Math.Pow(10,18)+1 will be true with mine... – Alecalecia

You bulletproof solution is not needed. Tested exhaustively and sort-of proven. – Swank

@Swank Your comment convinced me to downvote; the second block of code is apparently a bad idea, as it is a complex system that does the same as a much more simple one. – Jackstraw

@Yakk: Whereas I would say that the second piece of code is simpler in terms of being able to understand that it's definitely correct. Put it this way - I find the code here much simpler to understand than the maths in maaartinus' post on math.stackexchange. – Flu

I dunno. To be convinced the second one is correct, one must know that both BitConverter.DoubleToInt64Bits and BitConverter.Int64BitsToDouble cannot throw and is flawless, or that the wrapping code handles any exceptions perfectly. Understanding the linked proof is hard I'll agree; proving every single .net runtime you ever run on doesn't do something stupid is impossible! ;) But point taken. – Jackstraw

Answer 2

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

Anabelle

Answer 3

In Common Lisp, I use the following:

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

Aimeeaimil

Heh. Looking at https://mcmap.net/q/216894/-what-39-s-a-good-algorithm-to-determine-if-an-input-is-a-perfect-square-duplicate, 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). – Aimeeaimil

On SBCL, square should be expt: (defun perfect-square-p (n) (= (expt (isqrt n) 2) n)). – Udall

@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. – Aimeeaimil