94

重複の可能性：
整数の平方根が整数であるかどうかを判断する最速の方法

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

bool IsPerfectSquare(long input)
{
   // TODO
}

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

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

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

第二に、あなたが巨大でほぼ完全な正方形を持っているとき、doubleの精度は小さな値（.000 ... 00001）を失います。たとえば、私の実装はMath.Pow（10,18）+1のこのテストに失敗しました（私の実装はtrueと報告されています）。

4

3 に答える 3

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

これは、「平方根が整数であるか」をチェックするだけの問題のいくつかから逃れることができますが、すべてではない可能性があります。あなたは潜在的に少しファンキーになる必要があります：

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

厄介で、本当に大きな値以外には不要ですが、うまくいくはずです...

于 2008-12-05T13:41:05.167 に答える
12 
bool IsPerfectSquare(long input)
{
    long SquareRoot = (long) Math.Sqrt(input);
    return ((SquareRoot * SquareRoot) == input);
}
于 2008-12-05T13:42:24.493 に答える
9

Common Lispでは、私は以下を使用します：

(defun perfect-square-p (n)
  (= (expt (isqrt n) 2)
     n))
于 2008-12-05T13:45:56.293 に答える