什么是好的算法，以确定是否输入是一个完美的正方形？ [重复]

Question

  

<强>可能重复：结果   确定最快的方式，如果一个整数的平方根是整数

什么是方法，如果一个号码是完美的正方形？

bool IsPerfectSquare(long input)
{
   // TODO
}

我使用C＃但是这是与语言无关。

为了清楚和简化的奖励积分（这并不意味着是代码高尔夫球）。

---

编辑：：此得到了比我预想的要复杂得多！事实证明，与双精度的问题都表现在几个方面。首先，Math.Sqrt需要不能准确地持有长（感谢乔恩）双。

二，双精密将失去小值（.000 ... 00001）当你有一个巨大的，近乎完美的正方形。例如，我的实现失败这个试验Math.Pow（10,18）+1（矿报道真）。

Answer 1

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

这可以从一些的只是检查的问题逃脱“是平方根的整数”，但可能不是全部。您可能需要得到一点点funkier：

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))