我正在寻找确定长值是否为完美平方(即其平方根是另一个整数)的最快方法:
我使用内置的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。
你必须做一些基准测试。最佳算法将取决于输入的分布。
您的算法可能接近最佳,但在调用平方根例程之前,您可能需要快速检查以排除某些可能性。例如,通过按位“和”查看十六进制数字的最后一位。完美的正方形只能以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#代码几乎没有影响。
这是最简单和最简洁的方法,尽管我不知道它在CPU周期方面的比较。如果您只想知道根是否是整数,那么这非常有用。如果你真的关心它是不是整数,你也可以弄清楚。这里有一个简单(纯)函数:
private static final MathContext precision = new MathContext(20);
private static final Function<Long, Boolean> isRootWhole = (n) -> {
long digit = n % 10;
if (digit == 2 || digit == 3 || digit == 7 || digit == 8) {
return false;
}
return new BigDecimal(n).sqrt(precision).scale() == 0;
};
如果您不需要微优化,那么这个答案在简单性和可维护性方面更好。如果要计算负数,则需要相应地处理,并将绝对值发送到函数中。我包含了一个小的优化,因为由于二次残差mod 10,没有完美的正方形具有2、3、7或8的十位数。
在我的CPU上,在0-10000000上运行此算法平均每次计算需要1000-1100纳秒。
如果执行的计算次数较少,则早期的计算需要更长的时间。
我有一个负面评论,说我以前的编辑不适用于大量数据。OP提到了Longs,Long的最大完美正方形是9223372030926249001,因此该方法适用于所有Longs。