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

Question

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

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

bool IsPerfectSquare(long input)
{
   // TODO
}

我正在使用C#,但这与语言无关.

奖励点是为了清晰和简洁(这不是代码高尔夫).

---

编辑:这比我想象的要复杂得多!事实证明,双精度问题有两种表现形式.首先,Math.Sqrt采用了一个不能精确控制的长度(感谢Jon).

其次,当你拥有一个巨大的,接近完美的正方形时,双精度将失去小值(.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))