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

因此,我需要在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);
}

参考方案

该算法是bisection method用于查找多项式x2的零-n =0。为什么将(n / 32 + 8)用作种子?我不知道这是一个很差的近似值。 n.shiftRight(n.bitLength()/2);一个更好的近似值,几乎便宜的计算

45码