Qual è un buon algoritmo per determinare se un input è un quadrato perfetto? [duplicare]

Question

  

Possibile duplicato:
   Il modo più veloce per determinare se il quadrato di un numero intero root è un numero intero

Qual è un modo per vedere se un numero è un quadrato perfetto ?

bool IsPerfectSquare(long input)
{
   // TODO
}

Sto usando C # ma questo è il linguaggio agnostico.

Punti bonus per chiarezza e semplicità (questo non significa essere code-golf).

---

Modifica: Questo è diventato molto più complesso di quanto mi aspettassi! Si scopre che i problemi con doppia precisione si manifestano in un paio di modi. Innanzitutto, Math.Sqrt prende un doppio che non può contenere con precisione un lungo (grazie Jon).

In secondo luogo, la precisione di un doppio perderà piccoli valori (.000 ... 00001) quando hai un quadrato enorme, quasi perfetto. ad esempio, la mia implementazione non ha superato questo test per Math.Pow (10,18) +1 (il mio è stato riportato vero).

Answer 1

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

Questo potrebbe allontanarsi da alcuni dei problemi del solo controllo di "è la radice quadrata un numero intero" ma forse non tutto. Potenzialmente devi diventare un po 'più divertente:

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 non necessario per qualcosa di diverso da valori molto grandi, ma penso che dovrebbe funzionare ...

Answer 2

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

Answer 3

In Common Lisp, utilizzo quanto segue:

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