BigInteger算法是如何在内部工作的？

Question

Java的BigInteger divide在内部是如何工作的？我做了大量的研究却一无所获。因此，我对CPU如何进行除法做了一些研究，并研究了恢复/非恢复除法和快速除法算法等内容。但是，我不认为这些方法适用于BigInteger，因为BigInteger似乎必须利用Java原生操作。如果BigInteger像这些技术概述那样一点一点地做事情，那就太慢了。

Answer 1

OpenJDK的实现(是的，这是依赖于实现的)使用Knuth的“算法D”或Burnikel-Ziegler算法，这取决于除数和被除数有多大。如果除数很小，或者它们的大小相似，则使用前者。您可以查看源代码here。

public BigInteger divide(BigInteger val) {
    if (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
            mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
        return divideKnuth(val);
    } else {
        return divideBurnikelZiegler(val);
    }
}

• Algorithm D
• Burnikel-Ziegler Algorithm