#horner scheme

This is a bit of theory for our next steps. I posted this first as an answer to a new question (also by frodosamoa) How Can I Convert Very Large Decimal Numbers to Binary In Java on Stack Overflow.

The conversion between different number systems in principle is a repeated "division, remainder, multiply, add" operation. Let's look at an example:

We want to convert 123 from decimal to a base 3 number. What do we do?

Take the remainder modulo 3 - prepend this digit to the result.

Divide by 3.

If the number is bigger than 0, continue with this number at step 1

So it looks like this:

123 % 3 == 0. ⇒ The last digit is 0.

123 / 3 == 41.

41 % 3 == 2 ⇒ The second last digit is 2.

41 / 3 == 13

13 % 3 == 1 ⇒ The third digit is 1.

13 / 3 == 4

4 % 3 == 1 ⇒ The fourth digit is 1 again.

4 / 3 == 1

1 % 3 == 1 ⇒ The fifth digit is 1.

So, we have 11120 as the result.

The problem is that for this you need to have already some kind of division by 3 in decimal format, which is usually not the case if you don't implement your number in a decimal-based format.

But it works for converting from your internal number format to any external format.

So, let's look at how we would do the inverse calculation, from 11120 (base 3) to its decimal equivalent. (Base 3 is here the placeholder for an arbitrary radix, Base 10 the placeholder for your internal radix.) In principle, this number can be written as this:

1 * 3^4 + 1 * 3^3 + 1*3^2 + 2*3^1 + 0*3^0

A better way (faster to calculate) is this:

((((1 * 3) + 1 )*3 + 1 )*3 + 2)*3 + 0 1 3 4 12 13 39 41 123 123

(This is known as Horner scheme, usually used for calculating values of polynomials.)

You can implement this in the number scheme you are implementing, if you know how to represent the input radix (and the digits) in your target system.

In the next parts we will apply this to our DecimalBigInt class.