有什么好的算法可以确定输入是否为完美平方？[重复]

小编典典

有什么好的算法可以确定输入是否为完美平方？[重复]

algorithm

如何查看数字是否是一个完美的平方？

bool IsPerfectSquare(long input)
{
   // TODO
}

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

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

编辑： 这比我预期的要复杂得多！事实证明，双精度问题以多种方式体现出来。首先，Math.Sqrt取了一个不能精确容纳多久的双倍（感谢乔恩）。

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

阅读 191

2020-07-28

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

棘手的，除了真正大的值外，不需要其他任何事情，但是我认为它应该起作用…

2020-07-28