整数牛顿法

如果希望避免非整数运算，可以使用以下方法。它基本上使用了为整数运算而修改的牛顿法。

/**
 * 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的解决方案竞争。但是，可以通过使用其他文章中描述的过滤机制来提高其性能。

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

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

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

我在想我在数值分析课程中度过的可怕时光。

然后我记得，在Quake源代码中，有一个函数围绕着“网络”旋转：

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // wtf?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

它基本上使用牛顿近似函数（记不清确切的名字）计算平方根。

它应该是可用的，甚至可能更快，它来自一个非凡的id软件的游戏！

它是用C++编写的，但一旦你有了这样的想法，在Java中重用同样的技术应该不会太难：

我最初在以下位置找到它：http://www.codemaestro.com/reviews/9

牛顿的方法在维基百科上解释：http://en.wikipedia.org/wiki/Newton%27s_method

您可以通过链接了解更多的工作原理，但如果您不太在意，那么这大概是我在阅读博客和参加数值分析课程时所记得的：

*（long*）&y基本上是一个快速转换为long的函数，因此整数运算可以应用于原始字节。0x5f3759df-（i>>1）；line是近似函数的预先计算的种子值。*（float*）-i将值转换回浮点。y=y*（three-half-（x2*y*y））行基本上再次迭代函数上的值。

在结果上迭代函数的次数越多，逼近函数给出的值就越精确。在Quake的案例中，一次迭代“足够好”，但如果不是为了你。。。然后您可以添加所需的迭代次数。

这应该更快，因为它减少了在简单平方根中执行的除法运算的数量（实际上是一个*0.5F乘法运算），并用一些固定数量的乘法运算代替。

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

maartinus解决方案的以下简化似乎使运行时减少了几个百分点，但我在基准测试方面做得不够好，无法产生我可以信任的基准：

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    // Remove an even number of trailing zeros, leaving at most one.
    x >>= (Long.numberOfTrailingZeros(x) & (-2);
    // Repeat the test on the 6 least significant remaining bits.
    if (goodMask << x >= 0 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

值得检查的是，如何省略第一次测试，

if (goodMask << x >= 0) return false;

会影响性能。

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

复杂性为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;
}