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

Question

Possible en double:
Fastest way to determine if an integer's square root is an integer

Qu'est-ce qu'un moyen de voir si un nombre est un perfect square?

bool IsPerfectSquare(long input) 
{ 
    // TODO 
} 

J'utilise C# mais c'est la langue agnostique. Bonus points pour la clarté et la simplicité (ceci n'est pas destiné à être le code-golf).

---

Edit: cela a beaucoup plus complexe que prévu! Il s'avère que les problèmes de double précision se manifestent de deux manières. Premièrement, Math.Sqrt prend un double qui ne peut pas tenir longtemps (merci Jon). Deuxièmement, la précision d'un double va perdre de petites valeurs (.000 ... 00001) lorsque vous avez un énorme carré presque parfait. par exemple, ma mise en œuvre a échoué à ce test pour Math.Pow (10,18) +1 (la mienne a déclaré true).

Answer 1

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

Cela peut se éloigner de certains des problèmes de juste vérifier « est la racine carrée d'un nombre entier » mais peut-être pas tout. Vous avez besoin potentiellement d'obtenir un peu plus 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, et inutile pour autre chose que des valeurs très grandes, mais je pense qu'il devrait travail ...

Answer 2

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

Answer 3

En Common Lisp, j'utilise ce qui suit:

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