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

我使用内置的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中检查数组边界。


当前回答

当观察到正方形的最后n位时,我检查了所有可能的结果。通过连续检查更多位,可以消除多达5/6的输入。我实际上是为了实现费马的因子分解算法而设计的,而且速度非常快。

public static boolean isSquare(final long val) {
   if ((val & 2) == 2 || (val & 7) == 5) {
     return false;
   }
   if ((val & 11) == 8 || (val & 31) == 20) {
     return false;
   }

   if ((val & 47) == 32 || (val & 127) == 80) {
     return false;
   }

   if ((val & 191) == 128 || (val & 511) == 320) {
     return false;
   }

   // if((val & a == b) || (val & c == d){
   //   return false;
   // }

   if (!modSq[(int) (val % modSq.length)]) {
        return false;
   }

   final long root = (long) Math.sqrt(val);
   return root * root == val;
}

伪代码的最后一位可用于扩展测试以消除更多值。上述测试针对k=0、1、2、3

a的形式为(3<<2k)-1b的形式为(2<<2k)c的形式为(2<<2k+2)-1d的形式为(2<<2k-1)*10

它首先测试它是否具有幂模为2的平方残差,然后根据最终模量进行测试,然后使用Math.sqrt进行最终测试。我从最上面的帖子中提出了这个想法,并试图扩展它。我感谢任何评论或建议。

更新:使用模数(modSq)和44352的模数基数的测试,我的测试在OP更新中的96%的时间内运行,最多可达1000000000。

其他回答

整数问题需要整数解。因此

对(非负)整数进行二进制搜索,以找到最大的整数t,使t**2<=n。然后测试r**2=n是否精确。这需要时间O(log n)。

如果你不知道如何对正整数进行二进制搜索,因为集合是无界的,这很容易。首先计算二次幂的递增函数f(高于f(t)=t**2-n)。当你看到它变为正值时,你已经找到了一个上限。然后可以进行标准的二进制搜索。

使用牛顿的方法计算整数平方根,然后对这个数字进行平方并进行检查,这应该快得多,就像您在当前解决方案中所做的那样。牛顿方法是其他答案中提到的卡马克解的基础。你应该能够得到更快的答案,因为你只对根的整数部分感兴趣,这样你就可以更快地停止近似算法。

另一个可以尝试的优化:如果数字的数字根不以1、4、7或9这个数字不是一个完美的正方形。这可以作为在应用较慢的平方根算法之前消除60%输入的快速方法。

标签中提到了项目Euler,其中的许多问题需要检查数字>>2^64。当您使用80字节缓冲区时,上面提到的大多数优化都不容易工作。

我使用了javaBigInteger和稍微修改过的Newton方法,它对整数更有效。问题是,精确的平方n^2收敛到(n-1)而不是n,因为n^2-1=(n-1)(n+1),最终误差仅比最终除数低一步,算法终止。在计算错误之前,通过在原始参数中添加一个参数很容易解决。(为立方体根等添加两个)

这个算法的一个优点是,你可以立即判断出这个数字是否是一个完美的平方-牛顿方法中的最终误差(不是校正)将为零。一个简单的修改也可以让您快速计算floor(sqrt(x)),而不是最接近的整数。这对于几个Euler问题很方便。

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

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

为了记录在案,另一种方法是使用素分解。如果分解的每个因子都是偶数,那么这个数就是一个完美的平方。所以你想要的是看看一个数是否可以分解成质数平方的乘积。当然,你不需要获得这样的分解,只是为了看看它是否存在。

首先建立一个小于2^32的素数平方表。这远远小于一个包含所有整数的表,直到这个极限。

解决方案如下:

boolean isPerfectSquare(long number)
{
    if (number < 0) return false;
    if (number < 2) return true;

    for (int i = 0; ; i++)
    {
        long square = squareTable[i];
        if (square > number) return false;
        while (number % square == 0)
        {
            number /= square;
        }
        if (number == 1) return true;
    }
}

我想这有点神秘。它所做的是在每一步中检查质数的平方除以输入数。如果这样做了,那么它将尽可能地将数字除以平方,以从素数分解中删除这个平方。如果通过这个过程,我们得到1,那么输入数是素数平方的分解。如果平方比数字本身大,那么这个平方或任何更大的平方都无法分割它,所以数字不能是素数平方的分解。

考虑到现在的sqrt是在硬件中完成的,并且需要在这里计算素数,我想这个解决方案要慢得多。但正如mrzl在他的回答中所说,它应该比sqrt的解决方案给出更好的结果,sqrt的工作时间不会超过2^54。