大整数、平方根、java 和 C：这一行是做什么的？

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

我实现了这个例程，因为它简单且有效地使用了缓冲区 space。然而，因为它很简单，性能是无法接受的。当仅返回 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，如果不是，则将值打乱并重试。

大整数、平方根、java 和 C：这一行是做什么的？

Big integers, square root, java and C: What does this line do?

c

java

biginteger

sqrt