BigDecimal Architecture and Implementation

This page contains explanations of how different algorithms implemented in BigDecimal class work, and why they are there in the first place. This is a work in progress.

Contents

1. BigDecimal unlimited precision division

BigDecimal unlimited precision division

This only applies for unlimited precision, which is default behavior when no decimal mode is specified.

In all operations apart from division, we don't really care about preparing operands, because whatever combination of significands we have, the result of applying subtraction, addition or multiplication is going to be correct.

i.e.:

val a = "123".toBigDecimal() // significand = 123, precision = 3, exponent = 2 so 1.23E+2
val b = "456".toBigDecimal() // significand = 456, precision = 3, exponent = 2 so 4.56E+2

the multiplication is then executed as:

Take the significands and multiply them: 123*456 = 56088, 5 digits so the precision is going to be 5 in the end
Take the exponents and add them 2 + 2 = 4
Resulting BigDecimal: 5.6088E+4, significand = 56088, exponent = 4, precision = 5

There`s a bit more code to handle exponent in some corner cases but I'll skip that here

The exception is division, because significands are integers, they only support integer division, which creates two cases we need to worry about.

Case 1, division resulting in a remainder:

val a = Float.MIN_VALUE.toBigDecimal() // Creates a big decimal with significand 14
val divided = a / 10

If we didn't do any preparation of operands in division step and just let the BigInteger do the division the result would be 14 / 10 = 1 with a remainder 4 so we would get 1 as an answer and then need some special handling to continue dividing by using the remainder.

So to simplify the case when division results with a remainder we increase the precision of the dividend big decimal by creating a new big decimal by raising it to a certain power.

Currently the formula for that preparation is:

    val power = (other.precision * 2 + 6)
    val thisPrepared = this.significand * BigInteger.TEN.pow(power)

So what we created in the end is the prepared umber that has precision of firstOperand + (secondOperand * 2 + 6) in out example we had a precision of 2 for first operand and 2 for second operand so the prepared operand had precision of 12 (number of digits in 140000000000) Then if we divide by 10 we get 14000000000. The result is always correct, it's just that the precision has been increased.

Case 2, infinite division

This one is actually more important, consider the following case:

val a = 1.toBigDecimal()
val b = a / 3

The result of that division is mathematically 0.333... repeating to infinity, and we cannot really calculate that or represent it in memory. Because we are in unlimited precision mode we are claiming to the user that we will return a correct result no matter what are the operands. So to handle these situations we use the same approach as in case 1, we expand the precision of dividend by using the aforementioned formula and execute the division, in this case it would look like this

100000000 / 3 = 33333333 with remainder 1

And that remainder is telling us that we are in a situation where we cannot guarantee that the operation is going to end in finite time, so we throw an exception and ask the user to specify the decimal mode to his own satisfaction, here is the snippet that does that:

if (divRem.remainder != BigInteger.ZERO) {
                throw ArithmeticException("Non-terminating result of division operation " +
                        "(i.e. 1/3 = 0.3333... library needs to know when to stop and how to round up at that point). " +
                        "Specify decimalPrecision inside your decimal mode.")
            }