入力が完全な正方形であるかどうかを判断するのに適したアルゴリズムは何ですか？ [複製]

Question

  

可能な重複：
  整数の平方かどうかを判断する最も速い方法ルートは整数です

数値が完全な正方形であるかどうかを確認する方法は何ですか？

bool IsPerfectSquare(long input)
{
   // TODO
}

C＃を使用していますが、これは言語に依存しません。

明快さと単純さのボーナスポイント（これはコードゴルフを意図したものではありません）。

---

編集：これは予想以上に複雑になりました！倍精度の問題はいくつかの方法で明らかになります。まず、Math.Sqrtはlongを正確に保持できないdoubleを取ります（Jonに感謝）。

2番目に、巨大で完全に近い正方形がある場合、倍精度は小さな値（.000 ... 00001）を失います。たとえば、私の実装はMath.Pow（10,18）+1のこのテストに失敗しました（私の報告はtrueです）。

Answer 1

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

これは、<！> quot;平方根が整数である<！> quot;をチェックするだけの問題の一部から逃れることができます。おそらくすべてではありません。少しファンキーになる必要がある可能性があります：

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;
}

イッキーで、本当に大きな値以外には不要ですが、動作するはずです ...

Answer 2

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

Answer 3

Common Lispでは、次を使用します。

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