我正在寻找确定长值是否为完美平方（即其平方根是另一个整数）的最快方法：
我使用内置的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中检查数组边界。
我参加聚会已经很晚了，但我希望能提供一个更好的答案；更短，（假设我的基准是正确的）也更快。
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;
final int numberOfTrailingZeros = Long.numberOfTrailingZeros(x);
// Each square ends with an even number of zeros.
if ((numberOfTrailingZeros & 1) != 0) return false;
x >>= numberOfTrailingZeros;
// Now x is either 0 or odd.
// In binary each odd square ends with 001.
// Postpone the sign test until now; handle zero in the branch.
if ((x&7) != 1 | 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;
}
第一个测试很快捕捉到大多数非正方形。它使用一个长的64项表，因此没有数组访问成本（间接和边界检查）。对于均匀随机的长，有81.25%的概率在这里结束。
第二个测试捕获因式分解中奇数为2的所有数字。Long.numberOfTrailingZeros方法非常快，因为它被JIT编译成一条i86指令。
删除尾随零后，第三个测试处理以二进制形式的011、101或111结尾的数字，这些数字不是完美的正方形。它还关心负数，也处理0。
最后的测试是双倍算术。由于double只有53位尾数，从long到double的转换包括大值的舍入。尽管如此，测试是正确的（除非证明是错误的）。
试图结合mod255的想法并不成功。
关于卡马克方法，似乎只需要重复一次就很容易了，这应该会使精度位数翻倍。毕竟，这是一种极其简化的迭代方法——牛顿迭代法，具有很好的第一个猜测。
关于您当前的最佳状态，我看到了两个微观优化：
使用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;
显然，了解每个检查点有多少数字被剔除是很有意思的——我更怀疑这些检查是否真正独立，这使得事情变得棘手。
这是最简单和最简洁的方法，尽管我不知道它在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。
当观察到正方形的最后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。
这个问题让我很疑惑，所以我做了一些简单的编码，我在这里介绍它，因为我觉得它很有趣，很相关，但我不知道它有多有用。有一个简单的算法
a_n+1 = (a_n + x/a_n)/2
用于计算平方根，但它用于小数。我想知道，如果我只是用整数数学编码相同的算法，会发生什么。它甚至会汇聚到正确的答案上吗？我不知道，所以我写了一个程序。。。
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>
_Bool isperfectsquare(uint64_t x, uint64_t *isqrtx) {
// NOTE: isqrtx approximate for non-squares. (benchmarked at 162ns 3GHz i5)
uint32_t i;
uint64_t ai;
ai = 1 + ((x & 0xffff000000000000) >> 32) + ((x & 0xffff00000000) >> 24) + ((x & 0xffff0000) >> 16);
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = (ai + x/ai)/2;
ai = ai & 0xffffffff;
if (isqrtx != NULL) isqrtx[0] = ai;
return ai*ai == x;
}
void main() {
uint64_t x, isqrtx;
uint64_t i;
for (i=1; i<0x100000000; i++) {
if (!isperfectsquare(i*i, &isqrtx)) {
printf("Failed at %li", i);
exit(1);
}
}
printf("All OK.\n");
}
因此，事实证明，该公式的12次迭代足以为所有64位无符号长整数（完美平方）提供正确的结果，当然，非平方将返回false。
simon@simon-Inspiron-N5040:~$ time ./isqrt.bin
All OK.
real 11m37.096s
user 11m35.053s
sys 0m0.272s
因此697s/2^32约为162纳秒。实际上，该函数对于所有输入都具有相同的运行时。讨论中其他地方详细介绍的一些措施可以通过检查最后四位等来加快非正方形的速度。希望有人像我一样觉得这很有趣。
