标签中提到了项目Euler，其中的许多问题需要检查数字>>2^64。当您使用80字节缓冲区时，上面提到的大多数优化都不容易工作。

我使用了javaBigInteger和稍微修改过的Newton方法，它对整数更有效。问题是，精确的平方n^2收敛到（n-1）而不是n，因为n^2-1=（n-1）（n+1），最终误差仅比最终除数低一步，算法终止。在计算错误之前，通过在原始参数中添加一个参数很容易解决。（为立方体根等添加两个）

这个算法的一个优点是，你可以立即判断出这个数字是否是一个完美的平方-牛顿方法中的最终误差（不是校正）将为零。一个简单的修改也可以让您快速计算floor（sqrt（x）），而不是最接近的整数。这对于几个Euler问题很方便。

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

只需替换您的：

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);
}

如果速度是一个问题，为什么不将最常用的一组输入及其值划分到一个查找表中，然后执行您针对特殊情况提出的任何优化魔术算法？

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

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

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

当观察到正方形的最后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。

有人指出，完美正方形的最后d位只能取某些值。数字n的最后d位（以b为基数）与n除以bd时的余数相同，即C符号n%pow（b，d）。

这可以推广到任何模数m，即n%m可以用来排除某些百分比的数字是完全平方。您当前使用的模数是64，这允许12，即19%的余数作为可能的平方。通过一点编码，我找到了模数110880，它只允许2016，即1.8%的余数作为可能的平方。因此，根据模数运算（即除法）和查找表与机器上的平方根的成本，使用这个模数可能会更快。

顺便说一句，如果Java有办法为查找表存储一个压缩的位数组，那么不要使用它。现在110880个32位字的RAM不多，提取一个机器字将比提取一个位更快。