什么是确定输入是否是完美正方形的好算法？ [重复]-Java 学习之路

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

有什么方法可以查看数字是否为perfect square？

bool IsPerfectSquare(long input)
{
   // TODO
}

我正在使用C＃，但这与语言无关 .

奖励点是为了清晰和简单（这不是代码高尔夫） .

Edit: 这比我想象的要复杂得多！事实证明，双精度问题可以通过几种方式表现出来 . 首先，Math.Sqrt采用了一个不能精确控制的长度（感谢Jon） .

其次，当你拥有一个巨大的近乎完美的正方形时，双精度将失去小值（.000 ... 00001） . 例如，我的实现未通过Math.Pow（10,18）1的测试（我的报告为真） .

3 回答

106

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

这可能会避免一些仅仅检查"is the square root an integer"但可能不是全部的问题 . 你可能需要更有趣一点：

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，除了非常大的 Value 之外没有其他任何东西，但我认为它应该有用......

回复于 2024-04-20T03:18:58+08:00

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

回复于 2024-04-20T03:18:58+08:00

9
在Common Lisp中，我使用以下内容：
```
(defun perfect-square-p (n)
  (= (expt (isqrt n) 2)
     n))
```
回复于 2024-04-20T03:18:58+08:00

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

3 回答

相关问题