有人可以向我解释这个函数，该函数在Java中找到BigInteger的平方根吗？

Question

所以我需要在Java 9之前的版本中压缩BigInteger，我发现下面的函数可以做到这一点。我确实了解该代码，但是我真的不明白为什么要在那里。因此，我想我并没有真正了解其背后的数学原理。就像为什么要使用（n / 32 + 8）。为什么要计算中间值。等等

    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）仅用作“种子”，因为提供合理的起始值可以比仅选择任何数字提供更少的迭代次数，从而提供更好的近似值。

Answer 2

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

一种更好的近似值，几乎可以便宜地计算出