我正在寻找确定长值是否为完美平方（即其平方根是另一个整数）的最快方法：
我使用内置的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"
这是旧的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;
};
整数牛顿法
如果希望避免非整数运算，可以使用以下方法。它基本上使用了为整数运算而修改的牛顿法。
/**
* Test if the given number is a perfect square.
* @param n Must be greater than 0 and less
* than Long.MAX_VALUE.
* @return <code>true</code> if n is a perfect
* square, or <code>false</code> otherwise.
*/
public static boolean isSquare(long n)
{
long x1 = n;
long x2 = 1L;
while (x1 > x2)
{
x1 = (x1 + x2) / 2L;
x2 = n / x1;
}
return x1 == x2 && n % x1 == 0L;
}
此实现无法与使用Math.sqrt的解决方案竞争。但是，可以通过使用其他文章中描述的过滤机制来提高其性能。
