¿Qué es un buen algoritmo para determinar si una entrada es un cuadrado perfecto? [duplicar]

Question

  

Posible duplicado:
   La forma más rápida de determinar si un cuadrado entero root es un entero

¿Cuál es una manera de ver si un número es un cuadrado perfecto ?

bool IsPerfectSquare(long input)
{
   // TODO
}

Estoy usando C # pero esto es independiente del lenguaje.

Puntos de bonificación por claridad y simplicidad (esto no pretende ser código golf).

---

Editar: ¡Esto se volvió mucho más complejo de lo que esperaba! Resulta que los problemas con doble precisión se manifiestan de dos maneras. Primero, Math.Sqrt toma un doble que no puede contener con precisión un largo (gracias Jon).

Segundo, la precisión de un doble perderá valores pequeños (.000 ... 00001) cuando tenga un cuadrado enorme, casi perfecto. por ejemplo, mi implementación falló esta prueba para Math.Pow (10,18) +1 (la mía informó que es verdadera).

Answer 1

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

Esto puede alejarse de algunos de los problemas de solo verificar " es la raíz cuadrada un número entero " pero posiblemente no todos. Potencialmente necesita ser un poco más 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, e innecesario para cualquier cosa que no sean valores realmente grandes, pero creo que debería funcionar ...

Answer 2

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

Answer 3

En Common Lisp, uso lo siguiente:

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