我正在寻找确定长值是否为完美平方（即其平方根是另一个整数）的最快方法：
我使用内置的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中检查数组边界。
考虑到一般的比特长度（尽管我在这里使用了特定的类型），我试图设计如下的简单算法。最初需要对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;
}
如果你做了一个二进制斩试图找到“正确”的平方根，你可以很容易地检测到你得到的值是否足够接近：
(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次迭代。
我在想我在数值分析课程中度过的可怕时光。
然后我记得，在Quake源代码中，有一个函数围绕着“网络”旋转：
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // wtf?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
它基本上使用牛顿近似函数（记不清确切的名字）计算平方根。
它应该是可用的，甚至可能更快，它来自一个非凡的id软件的游戏！
它是用C++编写的，但一旦你有了这样的想法，在Java中重用同样的技术应该不会太难：
我最初在以下位置找到它：http://www.codemaestro.com/reviews/9
牛顿的方法在维基百科上解释：http://en.wikipedia.org/wiki/Newton%27s_method
您可以通过链接了解更多的工作原理，但如果您不太在意，那么这大概是我在阅读博客和参加数值分析课程时所记得的：
*（long*）&y基本上是一个快速转换为long的函数，因此整数运算可以应用于原始字节。0x5f3759df-（i>>1）；line是近似函数的预先计算的种子值。*（float*）-i将值转换回浮点。y=y*（three-half-（x2*y*y））行基本上再次迭代函数上的值。
在结果上迭代函数的次数越多，逼近函数给出的值就越精确。在Quake的案例中，一次迭代“足够好”，但如果不是为了你。。。然后您可以添加所需的迭代次数。
这应该更快，因为它减少了在简单平方根中执行的除法运算的数量（实际上是一个*0.5F乘法运算），并用一些固定数量的乘法运算代替。
