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

我使用内置的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+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1

因此,在计算了n^2之后,选项如下:

n ^2=目标:已完成,返回truen^2+2n+1>target>n^2:你很接近,但并不完美:return falsen^2-2n+1<目标<n^2:同上目标<n^2-2n+1:低位n上的二进制斩波目标>n^2+2n+1:较高n上的二进制斩波

(抱歉,这使用n作为您当前的猜测,并将其作为参数的目标。对此感到困惑深表歉意!)

我不知道这是否会更快,但值得一试。

编辑:二进制斩不必接受整个整数范围,或者(2^x)^2=2^(2x),所以一旦你在目标中找到了最高位(这可以用一个小技巧来完成;我完全忘记了怎么做),你就可以快速得到一系列可能的答案。请注意,一个简单的二进制斩仍然只需要31或32次迭代。

其他回答

maartinus解决方案的以下简化似乎使运行时减少了几个百分点,但我在基准测试方面做得不够好,无法产生我可以信任的基准:

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    // Remove an even number of trailing zeros, leaving at most one.
    x >>= (Long.numberOfTrailingZeros(x) & (-2);
    // Repeat the test on the 6 least significant remaining bits.
    if (goodMask << x >= 0 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

值得检查的是,如何省略第一次测试,

if (goodMask << x >= 0) return false;

会影响性能。

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

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

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

不确定这是否是最快的方法,但这是我(很久以前在高中)在数学课上无聊地玩计算器时偶然发现的。当时,我真的很惊讶这是有效的。。。

public static boolean isIntRoot(int number) {
    return isIntRootHelper(number, 1);
}

private static boolean isIntRootHelper(int number, int index) {
    if (number == index) {
        return true;
    }
    if (number < index) {
        return false;
    }
    else {
        return isIntRootHelper(number - 2 * index, index + 1);
    }
}

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

当观察到正方形的最后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。