java - BigInteger 算法如何在内部工作（Java）？

Question

Java 的 BigInteger 除法在内部是如何工作的？我进行了大量研究，但找不到任何东西。因此，我对 CPU 如何进行除法进行了一些研究，并研究了诸如恢复/非恢复除法和快速除法算法之类的东西。但是，我认为这些不适用于 BigInteger，因为 BigInteger 似乎必须使用 Java 的本机数字原始操作。如果 BigInteger 像这些技术大纲那样一点一点地做东西，那就太慢了。

标签： javabigintegerarbitrary-precision

Answer 1

OpenJDK 的实现（是的，这取决于实现）使用 Knuth 的“算法 D”或 Burnikel-Ziegler 算法，具体取决于除数和被除数的大小。如果除数很小，或者它们的大小相似，则使用前者。您可以在此处查看源代码。

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

• 算法 D
• 伯尼克尔-齐格勒算法