Qu'est-ce qu'un bon algorithme pour déterminer si une entrée est un carré parfait?

Question

Double Possible:
Le moyen le plus rapide pour déterminer si un nombre entier est la racine carrée est un nombre entier

Ce qui est une façon de voir si un nombre est un carré parfait?

bool IsPerfectSquare(long input)
{
   // TODO
}

Je suis à l'aide de C#, mais c'est la langue agnostique.

Les points de Bonus pour plus de clarté et de simplicité (ce n'est pas destiné à être code-golf).

---

Edit: C'est beaucoup plus complexe que ce que j'attendais! Il s'avère que les problèmes avec la double précision, se manifestent de deux façons. Tout D'Abord, Les Mathématiques.Sqrt prend un double qui ne peut pas précisément tenir un long (merci Jon).

Deuxièmement, un double de la précision va perdre les petites valeurs ( .000...00001) quand vous avez un énorme, près de carré parfait. par exemple, mon échec de la mise en œuvre de ce test de Mathématiques.Pow(10,18)+1 (mine a rapporté vrai).

Answer 1

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

Cela peut permettre d’éviter certains des problèmes de simplement vérifier que "la racine carrée est un entier", mais peut-être pas tous. Vous devez potentiellement devenir un peu plus funky:

 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, et inutile pour autre chose que de très grandes valeurs, mais je pense que ça devrait marcher ...

Answer 2

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

Answer 3

Dans Common Lisp, j'utilise ce qui suit:

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