algorithm - matematicos - ejemplos de algoritmos resueltos

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

Question

Posible duplicado:
La forma más rápida de determinar si la raíz cuadrada de un entero es un número entero

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

bool IsPerfectSquare(long input)
{
// TODO
}

Estoy usando C #, pero esto es independiente del idioma.

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 la doble precisión se manifiestan de dos maneras. Primero, Math.Sqrt toma un doble que no puede aguantar mucho (gracias Jon).

En segundo lugar, la precisión de un doble perderá valores pequeños (.000 ... 00001) cuando tenga un cuadrado enorme, casi perfecto. por ejemplo, mi implementación no pasó esta prueba para Math.Pow (10,18) +1 (la mía fue verdadera).

Answer 1

En Common Lisp, uso lo siguiente:

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

Answer 2

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

Answer 3

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

Esto puede alejarse de algunos de los problemas de simplemente verificar "es la raíz cuadrada un entero", pero posiblemente no todos. Es posible que necesites ser un poco más divertido:

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