CODEWITHSUNDEEP
javabigintegerarbitrary-precision
Joe C.
Joe C.

Reputation: 461

How does BigInteger algorithm work internally (Java)?

How does Java's BigInteger divide work internally? I did a ton of research and I can't find anything. So instead, I did some research into how CPUs do division, and looked into stuff like restoring/non-restoring division and fast division algorithms. However, I don't think these would work for BigInteger, because it seems like BigInteger has to make use of Java's native number primitive operations. If BigInteger did stuff bit by bit like these techniques outline, it would be too slow.

Upvotes: 2

Views: 446

Answers (1)

Sweeper
Sweeper

Reputation: 271355

OpenJDK's implementation (yes this is implementation-dependent) uses either Knuth's "Algorithm D", or the Burnikel-Ziegler Algorithm, depending on how big the divisor and the dividend are. If the divisor is small, or if they are both of similar magnitude, then the former is used. You can see the source code 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);
    }
}

Upvotes: 4

Related Questions