确定输入是否为完美正方形的好算法是什么? [英] What's a good algorithm to determine if an input is a perfect square?

问题描述

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

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

What's a way to see if a number is a perfect square?

bool IsPerfectSquare(long input)
{
   // TODO
}

我使用的是 C#，但这与语言无关.

I'm using C# but this is language agnostic.

清晰和简单的加分项(这并不意味着代码高尔夫).

Bonus points for clarity and simplicity (this isn't meant to be code-golf).

这比我预期的要复杂得多！事实证明，双精度的问题以几种方式表现出来.首先， Math.Sqrt 需要一个不能精确保持 long 的 double(感谢 Jon).

This got much more complex than I expected! It turns out the problems with double precision manifest themselves a couple ways. First, Math.Sqrt takes a double which can't precisely hold a long (thanks Jon).

第二，当你有一个巨大的、接近完美的正方形时，double 的精度会丢失小值 (.000...00001).例如，我的实现在 Math.Pow(10,18)+1 的测试中失败了(我的报告为真).

Second, a double's precision will lose small values ( .000...00001) when you have a huge, near perfect square. e.g., my implementation failed this test for Math.Pow(10,18)+1 (mine reported true).

推荐答案

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

这可能会避免一些仅仅检查平方根是一个整数"的问题，但可能不是全部.你可能需要变得更时髦一点:

This may get away from some of the problems of just checking "is the square root an integer" but possibly not all. You potentially need to get a little bit funkier:

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, and unnecessary for anything other than really large values, but I think it should work...

这篇关于确定输入是否为完美正方形的好算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！