谁能给我解释一下这个求 Java 中 BigInteger 的平方根的函数？

Question

所以我需要在 Java 9 之前对 BigInteger 进行 sqrt，我发现下面的函数可以做到这一点。我确实理解代码，但我真的不明白为什么它在那里。所以我想我并没有真正理解它背后的数学原理。比如为什么使用 (n / 32 + 8)。为什么 mid 是这样计算的。等等

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

Answer 1

编辑： ，这不是巴比伦法而是二分法。我在回答之前没有足够仔细地查看代码。请看他的回答，因为它比我的更准确。

这看起来是用于近似平方根的 Babylonian Method。 (n/32 + 8) 仅用作 "seed"，因为提供合理的起始值可以在更少的迭代中提供比仅选择任何数字更好的近似值。

Answer 2

该算法是 bisection method 应用于查找多项式 x² - 的零n=0。为什么 (n / 32 + 8) 用作种子？我不知道，因为这是一个相当差的近似值。 n.shiftRight(n.bitLength()/2);

谁能给我解释一下这个求 Java 中 BigInteger 的平方根的函数？

Can someone explain me this function that finds the square root of an BigInteger in Java?

java

biginteger

square-root