了解用于计算 Java 中的 BigInteger 平方根的基础 logic/maths

Question

我想在 Java 中计算 BigInteger 的平方根。在调查时，我发现这个很棒 link How can I find the Square Root of a Java BigInteger?，之前在 Whosebug 上问过。

提供了两个很棒的代码片段来解决这个问题。但是缺少底层逻辑或数学。

这是第一个:

BigInteger sqrt(BigInteger n) {
  BigInteger a = BigInteger.ONE;
  BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
  while(b.compareTo(a) >= 0) {
    BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
    if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(BigInteger.ONE);
    else a = mid.add(BigInteger.ONE);
  }
  return a.subtract(BigInteger.ONE);
}

取自here。

这是第二个：

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

由@EdwardFalk 回答。

为了主题的完整性，任何人都可以解释或指出基础数学或逻辑。

Answer 1

两者基本上是一个newton iteration。

但是第一个代码片段有一些奇怪的曲折，所以我会选择第二个代码片段。

了解用于计算 Java 中的 BigInteger 平方根的基础 logic/maths

Understanding underlying logic/maths for calculating BigInteger square root in Java

java

biginteger

square-root