java - 大整数、平方根、Java 和 C : What does this line do?

Question

我一直在做一些研究，寻找一种对大整数进行运算的相对快速的平方根算法。我在这里找到了几个例程。第一个(下面)是用 C 语言编写的...

int isqrt(int n)
{
  int b = 0;

  while(n >= 0)
  {
    n = n - b;
    b = b + 1;
    n = n - b;
  }

  return b - 1;
}

...我在这里找到:Looking for an efficient integer square root algorithm for ARM Thumb2

我实现了这个例程，因为它简单且可以有效利用缓冲区空间。然而，因为它很简单，性能是无法接受的。当只返回 b 而不是 b - 1 时，它确实有效并给出了正确的答案。

因此在寻求更好的算法时，我遇到了以下用 Java 编写的算法......

public static BigInteger sqrt(BigInteger x) {
    BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2);
    BigInteger div2 = div;
    // Loop until we hit the same value twice in a row, or wind
    // up alternating.
    for(;;) {
        BigInteger y = div.add(x.divide(div)).shiftRight(1);
        if (y.equals(div) || y.equals(div2))
            return y;
        div2 = div;
        div = y;
    }
}

...我在这个问题上找到的:How can I find the Square Root of a Java BigInteger?

我很乐意承认我不太精通 Java，所以我的问题是行 BigInteger y = div.add(x.divide(div)).shiftRight(1); 做什么？

以我有限的知识，我可以将循环转换为下面的 C 代码片段，但我对 Java 的了解还不够确定。

while (1)
{
    x /= div;
    div += x;
    y = x >> 1;

    if (y == div || y == div2) return(y);
    div2 = div;
    div = y;
}

这是正确的吗？

Answer 1

是的，这是正确的。

让我们翻译吧!

BigInteger y = div.add(x.divide(div)).shiftRight(1);
//becomes
long int y = (div + (x / div)) >> 1;
//this also applies to Java (you don't 'need' BigInteger or its fancy methods)

剩下的就很简单了。您只是比较以查看 y 是否等于 div 或 div2，如果不是，则将值打乱并重试。