我正在寻找确定长值是否为完美平方（即其平方根是另一个整数）的最快方法：
我使用内置的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中检查数组边界。
这是我能想到的最快的Java实现，使用了本线程中其他人建议的技术组合。
Mod-256测试不精确的mod-3465测试（避免以某些误报为代价的整数除法）浮点平方根，舍入并与输入值比较
我也尝试了这些修改，但它们对性能没有帮助：
附加mod-255测试将输入值除以4的幂快速逆平方根（要处理高N值，需要3次迭代，足以使其比硬件平方根函数慢。）
public class SquareTester {
public static boolean isPerfectSquare(long n) {
if (n < 0) {
return false;
} else {
switch ((byte) n) {
case -128: case -127: case -124: case -119: case -112:
case -111: case -103: case -95: case -92: case -87:
case -79: case -71: case -64: case -63: case -60:
case -55: case -47: case -39: case -31: case -28:
case -23: case -15: case -7: case 0: case 1:
case 4: case 9: case 16: case 17: case 25:
case 33: case 36: case 41: case 49: case 57:
case 64: case 65: case 68: case 73: case 81:
case 89: case 97: case 100: case 105: case 113:
case 121:
long i = (n * INV3465) >>> 52;
if (! good3465[(int) i]) {
return false;
} else {
long r = round(Math.sqrt(n));
return r*r == n;
}
default:
return false;
}
}
}
private static int round(double x) {
return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
}
/** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
private static final long INV3465 = 0x8ffed161732e78b9L;
private static final boolean[] good3465 =
new boolean[0x1000];
static {
for (int r = 0; r < 3465; ++ r) {
int i = (int) ((r * r * INV3465) >>> 52);
good3465[i] = good3465[i+1] = true;
}
}
}
如果最后的X位数字是N，那么应该可以更有效地包装“不能是完美的正方形”！我将使用java 32位int，并生成足够的数据来检查数字的最后16位，即2048个十六进制int值。
...
好吧。要么我遇到了一些超出我理解范围的数论，要么我的代码中有一个错误。无论如何，以下是代码：
public static void main(String[] args) {
final int BITS = 16;
BitSet foo = new BitSet();
for(int i = 0; i< (1<<BITS); i++) {
int sq = (i*i);
sq = sq & ((1<<BITS)-1);
foo.set(sq);
}
System.out.println("int[] mayBeASquare = {");
for(int i = 0; i< 1<<(BITS-5); i++) {
int kk = 0;
for(int j = 0; j<32; j++) {
if(foo.get((i << 5) | j)) {
kk |= 1<<j;
}
}
System.out.print("0x" + Integer.toHexString(kk) + ", ");
if(i%8 == 7) System.out.println();
}
System.out.println("};");
}
结果如下：
（ed：由于pretify.js性能不佳而取消；查看修订历史以查看。）
如果你做了一个二进制斩试图找到“正确”的平方根，你可以很容易地检测到你得到的值是否足够接近：
(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次迭代。
