一个数字的平方根，假设该数字是一个完全平方。

复杂性为log（n）

/**
 * Calculate square root if the given number is a perfect square.
 * 
 * Approach: Sum of n odd numbers is equals to the square root of n*n, given 
 * that n is a perfect square.
 *
 * @param number
 * @return squareRoot
 */

public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}

不知道最快，但最简单的方法是以正常方式取平方根，将结果乘以自身，看看它是否与原始值匹配。

由于我们在这里讨论的是整数，fasted可能涉及一个集合，您可以在其中进行查找。

用牛顿法计算平方根的速度快得惊人。。。只要起始值是合理的。然而，没有合理的起始值，在实践中，我们以平分和对数（2^64）行为结束。要真正做到快速，我们需要一种快速的方法来获得一个合理的初始值，这意味着我们需要进入机器语言。如果一个处理器在奔腾中提供了一个像POPCNT这样的指令，它对前导零进行计数，我们可以使用它来获得一个具有一半有效位的起始值。小心地，我们可以找到一个固定数量的牛顿步数，这将总是足够的。（因此，前面提到了需要循环并具有非常快的执行。）

第二种解决方案是通过浮点设备，它可能具有快速的sqrt计算（如i87协处理器）。即使通过exp（）和log（）进行偏移，也可能比牛顿退化为二进制搜索更快。这有一个棘手的方面，即依赖于处理器的分析，以确定后续是否需要改进。

第三种解决方案解决了一个稍有不同的问题，但很值得一提，因为问题中描述了情况。如果你想为稍有不同的数字计算很多平方根，你可以使用牛顿迭代，如果你从来没有重新初始化起始值，但只需将其保留在之前的计算停止的地方。我已经在至少一个欧拉问题中成功地使用了这一方法。

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的优化器必须很快地解决这一问题，所以我不怪他们。

你应该从一开始就去掉N的2次方部分。

第二次编辑下面m的神奇表达式应该是

m = N - (N & (N-1));

而不是书面的

第二次编辑结束

m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
  return false;

第一次编辑：

轻微改进：

m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
  return false;

第一次编辑结束

现在像往常一样继续。这样，当你到达浮点部分时，你已经去掉了所有2次方部分为奇数（大约一半）的数字，然后你只考虑剩下的1/8。也就是说，你在6%的数字上运行浮点部分。

这是我能想到的最快的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;
        }
    }

}