我正在寻找确定长值是否为完美平方(即其平方根是另一个整数)的最快方法:

我使用内置的Math.sqrt()以简单的方式完成了这项工作函数,但我想知道是否有一种方法可以通过将自己限制为仅限整数的域。维护查找表是不切实际的(因为平方小于263的231.5个整数)。

下面是我现在做的非常简单明了的方法:

public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

注意:我在许多Project Euler问题中都使用了这个函数。因此,其他人将永远不必维护此代码。而这种微优化实际上可能会有所不同,因为挑战的一部分是在不到一分钟的时间内完成每一个算法,而在某些问题中,这个函数需要调用数百万次。


我尝试了不同的解决方案:

经过详尽的测试,我发现不需要在Math.sqrt()的结果上加0.5,至少在我的机器上是这样。快速平方根逆运算速度更快,但对于n>=410881,它给出了错误的结果。然而,正如BobbyShaftoe所建议的,我们可以在n<410881时使用FISR黑客。牛顿的方法比Math.sqrt()慢得多。这可能是因为Math.sqr()使用了类似于牛顿方法的东西,但在硬件中实现,所以比Java快得多。此外,牛顿法仍然需要使用双精度。一个经过修改的牛顿方法使用了一些技巧,因此只涉及整数数学,需要一些技巧来避免溢出(我希望这个函数可以处理所有64位有符号的正整数),而且它仍然比math.sqrt()慢。二元斩更慢。这是有意义的,因为二进制斩波平均需要16次才能找到64位数字的平方根。根据John的测试,在C++中使用or语句比使用switch更快,但在Java和C#中,or和switch之间似乎没有区别。我还尝试创建一个查找表(作为64个布尔值的私有静态数组)。然后,我只说if(lookup[(int)(n&0x3F)]){test}else return false;,而不是switch或or语句;。令我惊讶的是,这(只是稍微)慢了一些。这是因为在Java中检查数组边界。


当前回答

整数牛顿法

如果希望避免非整数运算,可以使用以下方法。它基本上使用了为整数运算而修改的牛顿法。

/**
 * Test if the given number is a perfect square.
 * @param n Must be greater than 0 and less
 *    than Long.MAX_VALUE.
 * @return <code>true</code> if n is a perfect
 *    square, or <code>false</code> otherwise.
 */
public static boolean isSquare(long n)
{
    long x1 = n;
    long x2 = 1L;

    while (x1 > x2)
    {
        x1 = (x1 + x2) / 2L;
        x2 = n / x1;
    }

    return x1 == x2 && n % x1 == 0L;
}

此实现无法与使用Math.sqrt的解决方案竞争。但是,可以通过使用其他文章中描述的过滤机制来提高其性能。

其他回答

我不确定它是否会更快,甚至更准确,但你可以使用约翰·卡马克的神奇平方根算法来更快地解平方根。您可能很容易对所有可能的32位整数进行测试,并验证您实际上得到了正确的结果,因为这只是一个近似值。然而,现在我想起来,使用双打也是近似的,所以我不确定这会如何发挥作用。

如果你想要速度,考虑到整数的大小是有限的,我想最快的方法是(a)按大小划分参数(例如,按最大位集划分类别),然后对照该范围内的完美平方数组检查值。

我希望此功能与所有正64位有符号整数

Math.sqrt()使用double作为输入参数,因此对于大于2^53的整数,不会得到准确的结果。

用牛顿法计算平方根的速度快得惊人。。。只要起始值是合理的。然而,没有合理的起始值,在实践中,我们以平分和对数(2^64)行为结束。要真正做到快速,我们需要一种快速的方法来获得一个合理的初始值,这意味着我们需要进入机器语言。如果一个处理器在奔腾中提供了一个像POPCNT这样的指令,它对前导零进行计数,我们可以使用它来获得一个具有一半有效位的起始值。小心地,我们可以找到一个固定数量的牛顿步数,这将总是足够的。(因此,前面提到了需要循环并具有非常快的执行。)

第二种解决方案是通过浮点设备,它可能具有快速的sqrt计算(如i87协处理器)。即使通过exp()和log()进行偏移,也可能比牛顿退化为二进制搜索更快。这有一个棘手的方面,即依赖于处理器的分析,以确定后续是否需要改进。

第三种解决方案解决了一个稍有不同的问题,但很值得一提,因为问题中描述了情况。如果你想为稍有不同的数字计算很多平方根,你可以使用牛顿迭代,如果你从来没有重新初始化起始值,但只需将其保留在之前的计算停止的地方。我已经在至少一个欧拉问题中成功地使用了这一方法。

你必须做一些基准测试。最佳算法将取决于输入的分布。

您的算法可能接近最佳,但在调用平方根例程之前,您可能需要快速检查以排除某些可能性。例如,通过按位“和”查看十六进制数字的最后一位。完美的正方形只能以0、1、4或9结尾,以16为底。因此,对于75%的输入(假设它们是均匀分布的),可以避免调用平方根,以换取一些非常快的位旋转。

Kip对实现十六进制技巧的以下代码进行了基准测试。当测试数字1到100000000时,此代码的运行速度是原始代码的两倍。

public final static boolean isPerfectSquare(long n)
{
    if (n < 0)
        return false;

    switch((int)(n & 0xF))
    {
    case 0: case 1: case 4: case 9:
        long tst = (long)Math.sqrt(n);
        return tst*tst == n;

    default:
        return false;
    }
}

当我在C++中测试类似的代码时,它实际上比原始代码运行得慢。然而,当我消除switch语句时,十六进制技巧再次使代码速度提高了一倍。

int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h is the last hex "digit"
    if (h > 9)
        return 0;
    // Use lazy evaluation to jump out of the if statement as soon as possible
    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
    {
        int t = (int) floor( sqrt((double) n) + 0.5 );
        return t*t == n;
    }
    return 0;
}

消除switch语句对C#代码几乎没有影响。