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

Question

  

Double possible:
   Le moyen le plus rapide de déterminer si le carré d'un entier la racine est un entier

Comment savoir si un nombre est un carré parfait ?

bool IsPerfectSquare(long input)
{
   // TODO
}

J'utilise C # mais c'est une langue agnostique.

Des points bonus pour plus de clarté et de simplicité (il ne s'agit pas de code-golf).

Modifier: Cela est devenu beaucoup plus complexe que prévu! Il s'avère que les problèmes de double précision se manifestent de plusieurs manières. Tout d'abord, Math.Sqrt prend un double qui ne peut pas tenir longtemps (merci Jon).

Deuxièmement, la précision d'un double perdra de petites valeurs (.000 ... 00001) lorsque vous avez un carré énorme, presque parfait. Par exemple, mon implémentation a échoué à ce test pour Math.Pow (10,18) +1 (le mien a été déclaré vrai).

Answer 1

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

Cela peut permettre d’éviter certains les problèmes de simple vérification. "La racine carrée est-elle un entier"? mais peut-être pas tous. Vous devez potentiellement devenir un peu plus drôle:

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 cela devrait fonctionner ...

Answer 2

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

Answer 3

Dans Common Lisp, j’utilise les éléments suivants:

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