algorithm - 确定输入是否是完美正方形的好算法是什么？

Question

可能重复：
确定整数的平方根是否为整数的最快方法

有什么方法可以查看一个数字是否是一个完美的正方形？

bool IsPerfectSquare(long input)
{
   // TODO
}

我正在使用 C#，但这与语言无关。

清晰和简单的加分点（这并不意味着代码高尔夫）。

---

编辑：这比我预期的要复杂得多！事实证明，双精度的问题体现在几个方面。首先，Math.Sqrt 需要一个不能精确保持长的双精度（感谢乔恩）。

其次，当你有一个巨大的、近乎完美的正方形时，双精度会丢失小的值（0.000...00001）。例如，我的实现未通过 Math.Pow(10,18)+1 的此测试（我的报告为真）。

Answer 1

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

Icky，除了非常大的值之外，其他任何东西都是不必要的，但我认为它应该工作......

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