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

Community
  • 1
  • 1
Michael Haren
  • 105,752
  • 40
  • 168
  • 205
  • You could also google for the 'lsqrt' method used for integer square root. – leppie Dec 05 '08 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. – Vlad Gudim Dec 05 '08 at 14:37
  • To the solution you choose, don't forget to prepend a quick check for negativeness. – angus Dec 05 '08 at 13:51
  • Yes, I had that in there but removed it for brevity. Thanks for pointing it out though – Michael Haren Dec 05 '08 at 13:53
  • 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. – Vlad Gudim Dec 05 '08 at 13:45
  • 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: https://math.stackexchange.com/questions/4226869/how-well-does-this-method-of-checking-if-an-integer-n-is-a-square-perform – user25406 Aug 19 '21 at 19:52

3 Answers3

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

sakibmoon
  • 2,026
  • 3
  • 22
  • 32
Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • Looks as if you were faster than me ;-) Oops - your solution is also better, because 'closestRoot' is a far mor accurate name. – Treb Dec 05 '08 at 13:44
  • 28
    Love the number of upvotes I got *before* correcting it to a more bulletproof solution ;) – Jon Skeet Dec 05 '08 at 13:46
  • 197
    dude, you're jon skeet. – Epaga Dec 05 '08 at 13:48
  • 3
    @Jon: I'm thinking about rescinding my upvote. He asked for *clarity* and *simplicity*. :) – Bill the Lizard Dec 05 '08 at 13:49
  • 19
    I assumed accuracy was important. Otherwise I'd have gone for the "guaranteed to be random" kind of response :) – Jon Skeet Dec 05 '08 at 13:58
  • 2
    What's an example input that fails with your first method? – Michael Haren Dec 05 '08 at 14:02
  • Ah, I get it now. Math.Pow(10,18)+1 will be true with mine... – Michael Haren Dec 05 '08 at 14:03
  • 7
    You bulletproof solution is not needed. Tested exhaustively and [sort-of proven](http://math.stackexchange.com/q/237865/14435). – maaartinus Apr 27 '15 at 03:17
  • 1
    @maaartinus 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. – Yakk - Adam Nevraumont Nov 05 '15 at 19:37
  • 2
    @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. – Jon Skeet Nov 05 '15 at 19:47
  • 1
    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. – Yakk - Adam Nevraumont Nov 05 '15 at 21:11
12
bool IsPerfectSquare(long input)
{
    long SquareRoot = (long) Math.Sqrt(input);
    return ((SquareRoot * SquareRoot) == input);
}
sakibmoon
  • 2,026
  • 3
  • 22
  • 32
Treb
  • 19,903
  • 7
  • 54
  • 87
9

In Common Lisp, I use the following:

(defun perfect-square-p (n)
  (= (expt (isqrt n) 2)
     n))
Svante
  • 50,694
  • 11
  • 78
  • 122
  • Heh. Looking at http://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). – Svante Jan 15 '14 at 16:15
  • On SBCL, `square` should be `expt`: `(defun perfect-square-p (n) (= (expt (isqrt n) 2) n))`. – Ben Dec 11 '14 at 04:04
  • @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. – Svante Dec 11 '14 at 09:18