我正在寻找确定长值是否为完美平方（即其平方根是另一个整数）的最快方法：
我使用内置的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中检查数组边界。
这是最简单和最简洁的方法，尽管我不知道它在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。
这是旧的Marchant计算器算法（抱歉，我没有参考）从十进制到二进制的修改，在Ruby中，专门针对这个问题进行了修改：
def isexactsqrt(v)
value = v.abs
residue = value
root = 0
onebit = 1
onebit <<= 8 while (onebit < residue)
onebit >>= 2 while (onebit > residue)
while (onebit > 0)
x = root + onebit
if (residue >= x) then
residue -= x
root = x + onebit
end
root >>= 1
onebit >>= 2
end
return (residue == 0)
end
这里有一个类似的处理方法（可能有编码风格/气味或笨拙的O/O——重要的是算法，C++不是我的母语）。在这种情况下，我们要查找残数==0：
#include <iostream>
using namespace std;
typedef unsigned long long int llint;
class ISqrt { // Integer Square Root
llint value; // Integer whose square root is required
llint root; // Result: floor(sqrt(value))
llint residue; // Result: value-root*root
llint onebit, x; // Working bit, working value
public:
ISqrt(llint v = 2) { // Constructor
Root(v); // Take the root
};
llint Root(llint r) { // Resets and calculates new square root
value = r; // Store input
residue = value; // Initialise for subtracting down
root = 0; // Clear root accumulator
onebit = 1; // Calculate start value of counter
onebit <<= (8*sizeof(llint)-2); // Set up counter bit as greatest odd power of 2
while (onebit > residue) {onebit >>= 2; }; // Shift down until just < value
while (onebit > 0) {
x = root ^ onebit; // Will check root+1bit (root bit corresponding to onebit is always zero)
if (residue >= x) { // Room to subtract?
residue -= x; // Yes - deduct from residue
root = x + onebit; // and step root
};
root >>= 1;
onebit >>= 2;
};
return root;
};
llint Residue() { // Returns residue from last calculation
return residue;
};
};
int main() {
llint big, i, q, r, v, delta;
big = 0; big = (big-1); // Kludge for "big number"
ISqrt b; // Make q sqrt generator
for ( i = big; i > 0 ; i /= 7 ) { // for several numbers
q = b.Root(i); // Get the square root
r = b.Residue(); // Get the residue
v = q*q+r; // Recalc original value
delta = v-i; // And diff, hopefully 0
cout << i << ": " << q << " ++ " << r << " V: " << v << " Delta: " << delta << "\n";
};
return 0;
};
当观察到正方形的最后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。
sqrt调用并不完全准确，正如前面所提到的，但它很有趣，也很有启发性，因为它不会在速度方面影响其他答案。毕竟，sqrt的汇编语言指令序列很小。英特尔有一个硬件指令，我相信Java不会使用它，因为它不符合IEEE。
那么为什么速度慢呢？因为Java实际上是通过JNI调用一个C例程，而且这样做实际上比调用一个Java子程序慢，而Java子程序本身比内联调用慢。这很烦人，Java本应该想出更好的解决方案，即在必要时构建浮点库调用。哦，好吧。
在C++中，我怀疑所有复杂的替代方案都会失去速度，但我还没有检查过它们。我所做的，也是Java人会发现有用的，是一个简单的黑客，是a.Rex建议的特例测试的扩展。使用单个长值作为位数组，不检查边界。这样，您就有了64位布尔查找。
typedef unsigned long long UVLONG
UVLONG pp1,pp2;
void init2() {
for (int i = 0; i < 64; i++) {
for (int j = 0; j < 64; j++)
if (isPerfectSquare(i * 64 + j)) {
pp1 |= (1 << j);
pp2 |= (1 << i);
break;
}
}
cout << "pp1=" << pp1 << "," << pp2 << "\n";
}
inline bool isPerfectSquare5(UVLONG x) {
return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
}
在我的core2双人游戏机上，PerfectSquare5的程序运行时间约为1/3。我怀疑，沿着相同的路线进一步调整可能会进一步缩短平均时间，但每次检查时，你都在用更多的测试来换取更多的消除，所以你不能在这条路上走得太远。
当然，你可以用同样的方法检查高6位，而不是单独测试阴性。
请注意，我所做的只是消除可能的正方形，但当我有一个潜在的情况时，我必须调用原始的内联的isPerfectSquare。
init2例程被调用一次以初始化pp1和pp2的静态值。请注意，在我的C++实现中，我使用的是无符号long-long，因此，既然有符号，就必须使用>>>运算符。
没有内在的必要对数组进行边界检查，但Java的优化器必须很快地解决这一问题，所以我不怪他们。
考虑到一般的比特长度（尽管我在这里使用了特定的类型），我试图设计如下的简单算法。最初需要对0,1,2或<0进行简单而明显的检查。以下是简单的，因为它不试图使用任何现有的数学函数。大多数运算符可以用逐位运算符替换。我还没有用任何基准数据进行测试。我既不是数学专家，也不是计算机算法设计专家，我很乐意看到你们指出这个问题。我知道那里有很多改进的机会。
int main()
{
unsigned int c1=0 ,c2 = 0;
unsigned int x = 0;
unsigned int p = 0;
int k1 = 0;
scanf("%d",&p);
if(p % 2 == 0) {
x = p/2;
}
else {
x = (p/2) +1;
}
while(x)
{
if((x*x) > p) {
c1 = x;
x = x/2;
}else {
c2 = x;
break;
}
}
if((p%2) != 0)
c2++;
while(c2 < c1)
{
if((c2 * c2 ) == p) {
k1 = 1;
break;
}
c2++;
}
if(k1)
printf("\n Perfect square for %d", c2);
else
printf("\n Not perfect but nearest to :%d :", c2);
return 0;
}
