为了记录在案，另一种方法是使用素分解。如果分解的每个因子都是偶数，那么这个数就是一个完美的平方。所以你想要的是看看一个数是否可以分解成质数平方的乘积。当然，你不需要获得这样的分解，只是为了看看它是否存在。

首先建立一个小于2^32的素数平方表。这远远小于一个包含所有整数的表，直到这个极限。

解决方案如下：

boolean isPerfectSquare(long number)
{
    if (number < 0) return false;
    if (number < 2) return true;

    for (int i = 0; ; i++)
    {
        long square = squareTable[i];
        if (square > number) return false;
        while (number % square == 0)
        {
            number /= square;
        }
        if (number == 1) return true;
    }
}

我想这有点神秘。它所做的是在每一步中检查质数的平方除以输入数。如果这样做了，那么它将尽可能地将数字除以平方，以从素数分解中删除这个平方。如果通过这个过程，我们得到1，那么输入数是素数平方的分解。如果平方比数字本身大，那么这个平方或任何更大的平方都无法分割它，所以数字不能是素数平方的分解。

考虑到现在的sqrt是在硬件中完成的，并且需要在这里计算素数，我想这个解决方案要慢得多。但正如mrzl在他的回答中所说，它应该比sqrt的解决方案给出更好的结果，sqrt的工作时间不会超过2^54。

我希望此功能与所有正64位有符号整数

Math.sqrt（）使用double作为输入参数，因此对于大于2^53的整数，不会得到准确的结果。

我喜欢对一些输入使用几乎正确的方法。这是一个“偏移”更高的版本。代码似乎有效，并通过了我的简单测试用例。

只需替换您的：

if(n < 410881L){...}

使用此代码：

if (n < 11043908100L) {
    //John Carmack hack, converted to Java.
    // See: http://www.codemaestro.com/reviews/9
    int i;
    float x2, y;

    x2 = n * 0.5F;
    y = n;
    i = Float.floatToRawIntBits(y);
    //using the magic number from 
    //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
    //since it more accurate
    i = 0x5f375a86 - (i >> 1);
    y = Float.intBitsToFloat(i);
    y = y * (1.5F - (x2 * y * y));
    y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate

    sqrt = Math.round(1.0F / y);
} else {
    //Carmack hack gives incorrect answer for n >= 11043908100.
    sqrt = (long) Math.sqrt(n);
}

这个问题让我很疑惑，所以我做了一些简单的编码，我在这里介绍它，因为我觉得它很有趣，很相关，但我不知道它有多有用。有一个简单的算法

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纳秒。实际上，该函数对于所有输入都具有相同的运行时。讨论中其他地方详细介绍的一些措施可以通过检查最后四位等来加快非正方形的速度。希望有人像我一样觉得这很有趣。

如果你想要速度，考虑到整数的大小是有限的，我想最快的方法是（a）按大小划分参数（例如，按最大位集划分类别），然后对照该范围内的完美平方数组检查值。

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

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

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