确定整数平方根是否为整数的最快方法

Question

确定整数平方根是否为整数的最快方法

我在寻找最快的方法来确定long值是一个完全平方(即它的平方根是另一个整数)：

1. 我用简单的方法，使用内置的

   Math.sqrt()

   函数，但我想知道是否有一种方法可以通过将自己限制在仅为整数的域来更快地完成它。
2. 维护查找表是不切实际的(因为大约有2

   ^31.5

   平方小于2的整数

   ⁶³).

下面是我现在所做的非常简单和直接的方法：

public final static boolean isPerfectSquare(long n){
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;}

_{注意：我在很多场合都使用这个函数Euler项目问题。所以没有其他人需要维护这段代码。而这种微观优化实际上会产生影响，因为挑战的一部分是在不到一分钟的时间内完成每一种算法，在某些问题中，这个函数需要被调用数百万次。}

---

我尝试了解决这个问题的不同方法：

• 经过详尽的测试，我发现

  0.5

  对于Math.sqrt()的结果是不必要的，至少在我的机器上是不需要的。
• 这个

  快速逆平方根

  虽然速度更快，但在n>=410881时却给出了不正确的结果。然而，正如

  博比·沙夫托

  ，我们可以在n<410881的情况下使用FISR黑客。
• 牛顿的方法比

  Math.sqrt()

  ..这可能是因为

  Math.sqrt()

  使用类似于Newton的方法，但在硬件中实现，因此它比Java快得多。此外，牛顿的方法仍然需要使用双倍。
• 一种改进的牛顿方法，它使用了一些技巧，因此只涉及整数数学，它需要一些黑客来避免溢出(我希望这个函数可以处理所有64位的正数带符号整数)，它仍然比

  Math.sqrt().

• 二进制印章甚至更慢。这是有意义的，因为二进制CHOP平均需要16次才能找到64位数的平方根。
• 根据约翰的测试

  or

  语句在C+中比使用

  switch

  ，但在Java和C#中，

  or

  和

  switch.

• 我还尝试创建一个查找表(作为一个由64个布尔值组成的私有静态数组)。然后，而不是要么切换，要么

  or

  声明，我只想说

  if(lookup[(int)(n&0x3F)]) { test } else return false;

  ..令我惊讶的是，这样做(只是稍微)慢了一些。这是因为

  数组边界在Java中被检查.

Answer 1

你得做一些基准测试。最佳算法将取决于输入的分布。您的算法可能几乎是最优的，但是您可能需要在调用平方根例程之前做一次快速检查，排除一些可能性。例如，看看你的十六进制数字的最后一个数字，做一些明智的“和”。完美方格只能以0、1、4或9为底16结尾，因此对于75%的输入(假设它们是均匀分布的)，您可以避免对平方根的调用，以换取一些非常快的位旋转。Kip对以下实现十六进制技巧的代码进行了基准测试。当测试数字1到100，000，000时，此代码的运行速度是原始代码的两倍。public&nbsp;final&nbsp;static&nbsp;boolean&nbsp;isPerfectSquare(long&nbsp;n){ &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(n&nbsp;<&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;switch((int)(n&nbsp;&&nbsp;0xF)) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;case&nbsp;0:&nbsp;case&nbsp;1:&nbsp;case&nbsp;4:&nbsp;case&nbsp;9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;long&nbsp;tst&nbsp;=&nbsp;(long)Math.sqrt(n); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;tst*tst&nbsp;==&nbsp;n; &nbsp;&nbsp;&nbsp;&nbsp;default: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;}}当我在C+中测试类似的代码时，它的运行速度实际上比原来的要慢。但是，当我删除开关语句时，十六进制技巧再次使代码速度提高了一倍。int&nbsp;isPerfectSquare(int&nbsp;n){ &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;h&nbsp;=&nbsp;n&nbsp;&&nbsp;0xF;&nbsp;&nbsp;//&nbsp;h&nbsp;is&nbsp;the&nbsp;last&nbsp;hex&nbsp;"digit" &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(h&nbsp;>&nbsp;9) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;Use&nbsp;lazy&nbsp;evaluation&nbsp;to&nbsp;jump&nbsp;out&nbsp;of&nbsp;the&nbsp;if&nbsp;statement&nbsp;as&nbsp;soon&nbsp;as&nbsp;possible &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(h&nbsp;!=&nbsp;2&nbsp;&&&nbsp;h&nbsp;!=&nbsp;3&nbsp;&&&nbsp;h&nbsp;!=&nbsp;5&nbsp;&&&nbsp;h&nbsp;!=&nbsp;6&nbsp;&&&nbsp;h&nbsp;!=&nbsp;7&nbsp;&&&nbsp;h&nbsp;!=&nbsp;8) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;t&nbsp;=&nbsp;(int)&nbsp;floor(&nbsp;sqrt((double)&nbsp;n)&nbsp;+&nbsp;0.5&nbsp;); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;t*t&nbsp;==&nbsp;n; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;}删除Switch语句对C#代码几乎没有影响。