一个好的算法来确定输入是否为完全平方数是什么？

Question

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

如何判断一个数字是不是完全平方数？

bool IsPerfectSquare(long input)
{
   // TODO
}

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

如果能够更加清晰简洁，就会得到额外的分数（这不是代码竞赛）。

---

编辑：这比我预料的要复杂得多！双精度问题表现出来的方式有几种。首先，Math.Sqrt采用double类型，无法精确保存long类型（感谢Jon）。

其次，在你有一个巨大的、接近完美平方的数时，double类型的精度会丢失小的值（.000...00001）。例如，我的实现未通过Math.Pow(10, 18)+1的测试（我的实现报告为true）。

- Michael Haren

---

有一个非常相似的问题。请参考https://dev59.com/X3VC5IYBdhLWcg3wbglT，这里有一个很好的答案。 - Vlad Gudim

在你选择的解决方案中，不要忘记在前面添加一个快速检查负数的步骤。 - angus

是的，我之前加了这个，但为了简洁起见把它移除了。不过感谢你指出来。 - Michael Haren

你也可以在谷歌上搜索“lsqrt”方法，用于整数平方根。 - leppie

Michael，Bill the Lizard提出了一个很好的观点，即这只是一个类似的问题，而不是完全重复的问题。我认为这个问题不需要关闭。 此外，完全平方数的问题在实际情况下比看起来更加复杂，而这里的答案也做出了一些很好的贡献。 - Vlad Gudim

我不知道这个方法判断一个整数是否为完全平方数的速度有多快。该方法不使用平方根或牛顿法。可以在此处找到该方法： https://math.stackexchange.com/questions/4226869/how-well-does-this-method-of-checking-if-an-integer-n-is-a-square-perform - user25406

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

对于除了非常大的值以外，这个东西很不好用，但是我认为它应该能够工作...

- Jon Skeet

---

喜欢在更改为更可靠的解决方案之前获得的点赞数;) - Jon Skeet

老兄，你就是Jon Skeet。 - Epaga

@Jon：我在考虑取消我的点赞。他要求的是清晰和简明。 :) - Bill the Lizard

我认为准确性很重要。否则我就会选择“保证是随机的”这种回答方式 :) - Jon Skeet

您不需要防弹方案。这已经经过彻底测试并有点证明。 - maaartinus

Answer 2

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

- Treb

Answer 3

在Common Lisp中，我使用以下内容：

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

- Harleqin

---

看了一下https://dev59.com/j3RC5IYBdhLWcg3wS_EF#343862，我应该补充说明Common Lisp有一个“完整”的数字堆栈，因此对于任何非负整数（当然受工作内存限制）都可以正常运行。 - Svante

在SBCL中，“square”应该是“expt”：(defun perfect-square-p (n) (= (expt (isqrt n) 2) n))。 - Ben

@BenSima：实际上，由于“square”未在标准中定义，您需要在任何实现中定义（或替换）它。我编辑了答案，以免出现这种依赖关系。 - Svante