我正在寻找确定长值是否为完美平方(即其平方根是另一个整数)的最快方法:
我使用内置的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中检查数组边界。
这里有一个分而治之的解决方案。
如果自然数(数字)的平方根是自然数(解),您可以根据数字的位数轻松确定解的范围:
数字有1位:范围内的解=1-4数字有2位数:范围内的解=3-10数字有3位数:范围内的解=10-40数字有4位数字:范围=30-100数字有5位数:范围内的解=100-400
注意到重复了吗?
您可以在二进制搜索方法中使用此范围,以查看是否存在以下解决方案:
number == solution * solution
这是密码
这是我的类SquareRootChecker
public class SquareRootChecker {
private long number;
private long initialLow;
private long initialHigh;
public SquareRootChecker(long number) {
this.number = number;
initialLow = 1;
initialHigh = 4;
if (Long.toString(number).length() % 2 == 0) {
initialLow = 3;
initialHigh = 10;
}
for (long i = 0; i < Long.toString(number).length() / 2; i++) {
initialLow *= 10;
initialHigh *= 10;
}
if (Long.toString(number).length() % 2 == 0) {
initialLow /= 10;
initialHigh /=10;
}
}
public boolean checkSquareRoot() {
return findSquareRoot(initialLow, initialHigh, number);
}
private boolean findSquareRoot(long low, long high, long number) {
long check = low + (high - low) / 2;
if (high >= low) {
if (number == check * check) {
return true;
}
else if (number < check * check) {
high = check - 1;
return findSquareRoot(low, high, number);
}
else {
low = check + 1;
return findSquareRoot(low, high, number);
}
}
return false;
}
}
下面是一个如何使用它的示例。
long number = 1234567;
long square = number * number;
SquareRootChecker squareRootChecker = new SquareRootChecker(square);
System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true"
long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"
为了记录在案,另一种方法是使用素分解。如果分解的每个因子都是偶数,那么这个数就是一个完美的平方。所以你想要的是看看一个数是否可以分解成质数平方的乘积。当然,你不需要获得这样的分解,只是为了看看它是否存在。
首先建立一个小于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。
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;
会影响性能。
关于卡马克方法,似乎只需要重复一次就很容易了,这应该会使精度位数翻倍。毕竟,这是一种极其简化的迭代方法——牛顿迭代法,具有很好的第一个猜测。
关于您当前的最佳状态,我看到了两个微观优化:
使用mod255在检查后移动检查而不是0重新排列4的除法幂,以跳过通常(75%)情况下的所有检查。
I.e:
// Divide out powers of 4 using binary search
if((n & 0x3L) == 0) {
n >>=2;
if((n & 0xffffffffL) == 0)
n >>= 32;
if((n & 0xffffL) == 0)
n >>= 16;
if((n & 0xffL) == 0)
n >>= 8;
if((n & 0xfL) == 0)
n >>= 4;
if((n & 0x3L) == 0)
n >>= 2;
}
更好的方法可能是
while ((n & 0x03L) == 0) n >>= 2;
显然,了解每个检查点有多少数字被剔除是很有意思的——我更怀疑这些检查是否真正独立,这使得事情变得棘手。