O que é um bom algoritmo para determinar se uma entrada é um quadrado perfeito? [duplicado]

Question

Duplicate possíveis:
maneira mais rápida para determinar se quadrado de um inteiro raiz é um inteiro

O que é uma maneira de ver se um número é um perfeito quadrado?

bool IsPerfectSquare(long input)
{
   // TODO
}

Eu estou usando C #, mas este é agnóstico linguagem.

Os pontos de bónus para clareza e simplicidade (isto não é feito para ser código-golf).

---

Editar: Isto ficou muito mais complexo do que eu esperava! Acontece que os problemas com dupla manifesto precisão-se algumas maneiras. Primeiro, Math.Sqrt leva um casal que não consegue segurar precisamente longos (graças Jon).

Em segundo lugar, a precisão de um duplo perderá valores pequenos (0,000 ... 00001) quando você tem uma enorme, perto quadrado perfeito. por exemplo, minha implementação falhou este teste para Math.pow (10,18) +1 (mina relatou true).

Answer 1

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

Isto pode ficar longe de alguns dos problemas de apenas verificar "é a raiz quadrada de um número inteiro", mas possivelmente não todos. Você potencialmente precisa obter um funkier bit pouco:

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 desnecessário para outra coisa senão valores muito grandes, mas eu acho que deve trabalho ...

Answer 2

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

Answer 3

Em Lisp comum, eu uso o seguinte:

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