#big-numbers-selfmade

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.

Let's remember, the constructor looked like this:

/** * creates a DecimalBigInt based on an array of digits. * @param digits a list of digits, each between 0 (inclusive) * and {@link #RADIX} (exclusive). * @throws IllegalArgumentException if any digit is out of range. */ public DecimalBigInt(int... digits) { for(int digit : digits) { if(digit < 0 || RADIX <= digit) { throw new IllegalArgumentException("digit " + digit + " out of range!"); } } this.digits = digits.clone(); }

If digits starts with zeros, we have a longer representation for the same number. This does not only eats away memory, but also gives problems for our comparison method in part 7 (and the equals method, which will come soon).

Thus, if we are already looping through the array to complain on illegal digits, we can also look if there are leading zeros, and if so, cut them off.

/** * creates a DecimalBigInt based on an array of digits. * @param digits a list of digits, each between 0 (inclusive) * and {@link RADIX} (exclusive). * @throws IllegalArgumentException if any digit is out of range. */ public DecimalBigInt(int... digits) { // we count how much leading zeroes there are. int zeroCount = 0; // zero == until now no nonzero digit seen. boolean zero = true; for(int digit : digits) { if(digit < 0 || RADIX <= digit) { throw new IllegalArgumentException("digit " + digit + " out of range!"); } if(zero) { if (digit != 0) { zero = false; } else { zeroCount ++; } } } // cut off leading zeros by copying only the rest. // (We always do the copying, since we want to be independent // from the input array.) this.digits = Arrays.copyOfRange(digits, zeroCount, digits.length); }

Now we also can omit this cut-off code in the [plus()][Part 4: addition] and [times()][Part 5: multiplication] methods, which get simpler now.

We want to be able to compare two of our objects - for example, to use them as keys in a SortedMap or similar structure. So, we implement Comparable<DecimalBigInt> and its compareTo method.

This method should return 0 if the compared objects are equal, a negative value if this is smaller than that and a positive value if this is bigger than that.

public int compareTo(DecimalBigInt that) {

How to know if one of our numbers is bigger than another? First, we compare the length of the arrays. As we took care not to induce any leading zeros (did we?), the longer array should have the bigger number.

if(this.digits.length < that.digits.length) { return -1; } if (that.digits.length < this.digits.length) { return 1; }

If the length are same, we can compare digit-wise. Since we use big endian representation (i.e. the big end comes first), we start at the beginning.

for(int i = 0; i < this.digits.length; i++) { if(this.digits[i] < that.digits[i]) { return -1; } if(that.digits[i] < this.digits[i]) { return 1; } }

If everything was same, obviously our numbers are identical, and we can return 0.

return 0; }

Actually, we did not yet make sure there are no leading zeros: we will do this in the next part.

Here the factorial function:

/** * calculates the factorial of an int number. * This uses a simple iterative loop. */ public static DecimalBigInt factorial(int n) { DecimalBigInt fac = new DecimalBigInt(1); for(int i = 2; i <= n; i++) { fac = fac.times(new DecimalBigInt(i)); } return fac; }

This gives us

fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000

We don't really want to use a DecimalBigInt as input, as this simple implementation takes already too long for larger int values (and needs lots of memory, too).

For the original question this would be enough, but we want a more usable class. The next parts will add more useful methods.

Let's remember back to school, how did we multiply bigger numbers on paper?

123 * 123 ---------- 369 <== 123 * 3 246 <== 123 * 2 123 <== 123 * 1 -------- 15129

So, we have to multiply each digit[i] of the first number with each digit[j] of the second number, and add the product in digit[i+j] of the result (and pay attention to carry). Of course, here the indexes are counted from right, not from left. (Now i really wish I had used little-endian numbers.)

Since the product of two of our digits can get outside of the range of int, we use long for multiplication.

/** * multiplies two digits and adds the product to the result array * at the right digit-position. */ private void multiplyDigit(int[] result, int resultIndex, int firstFactor, int secondFactor) { long prod = (long)firstFactor * (long)secondFactor; int prodDigit = (int)(prod % RADIX); int carry = (int)(prod / RADIX); addDigits(result, resultIndex, carry, prodDigit); }

Now we can see why I declared my addDigits method to take a resultIndex parameter. (And I just changed the last argument to a varargs parameter, to be able to write this here easier.)

So, here the cross-multiplying method:

private void multiplyDigits(int[] result, int resultIndex, int[] leftFactor, int[] rightFactor) { for(int i = 0; i < leftFactor.length; i++) { for(int j = 0; j < rightFactor.length; j++) { multiplyDigit(result, resultIndex - (i + j), leftFactor[leftFactor.length-i-1], rightFactor[rightFactor.length-j-1]); } } }

I hope I have the index-calculations right. With a little-endian representation, it would have been multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j]) - quite clearer, isn't it?

Our times method now has only to allocate the result array, invoke multiplyDigits and wrap the result.

/** * returns the product {@code this × that}. */ public DecimalBigInt times(DecimalBigInt that) { int[] result = new int[this.digits.length + that.digits.length]; multiplyDigits(result, result.length-1, this.digits, that.digits); // cut off leading zero, if any if(result[0] == 0) { result = Arrays.copyOfRange(result, 1, result.length); } return new DecimalBigInt(result); }

For testing, d2.times(d2) gives Big[152, 415787532, 388367501, 905199875, 19052100], which is the same what my Emacs calc calculates here.

This is already enough to calculate big factorials, as we will see in the next part.

Now that we can convert our numbers from and to decimal strings, we should also add some arithmetic operations.

Let's start with addition, as this is simple (and we can use parts of it for the multiplication later).

/** * calculates the sum of this and that. */ public DecimalBigInt plus(DecimalBigInt that) { ... }

I want method names that you can read like you would read the formula, thus plus, minus, times instead of add, subtract, multiply.

So, how does addition work? It works the same as we learned it in school for decimal numbers higher than 9: add the corresponding digits, and if for some of then the result is bigger than 10 (or RADIX in our case), carry one to the next digit. This can cause the resulting number to have one digit more than the original ones.

First we look at the simple case that both numbers have same number of digits. Then it looks simply like this:

int[] result = new int[this.digits.length]; int carry = 0; for(int i = this.digits.length-1; i > 0; i--) { int digSum = carry + this.digits[i] + that.digits[i]; result[i] = digSum % RADIX; carry = digSum / RADIX; } if(carry > 0) { int[] temp = new int[result.length + 1]; System.arraycopy(result, 0, temp, 1, result.length); temp[0] = carry; result = temp; } return new DecimalBigInt(result);

(We go from right to left, so we can carry any overflows to the next digit. This would be a bit prettier if we had decided using little endian format.)

If both numbers do not have the same number of digits, it gets a bit more complicated.

To let it as simple as possible, we split it to several methods:

This method adds one digit to an element in the array (which may already contain some non-zero value), and stores the result back in the array. If there was overflow, we carry it to the next digit (which has index one less, not one more) by means of a recursive call. This way we make sure our digits stay always in the valid range.

/** * adds one digit from the addend to the corresponding digit * of the result. * If there is carry, it is recursively added to the next digit * of the result. */ private void addDigit(int[] result, int resultIndex, int addendDigit) { int sum = result[resultIndex] + addendDigit; result[resultIndex] = sum % RADIX; int carry = sum / RADIX; if(carry > 0) { addDigit(result, resultIndex - 1, carry); } }

The next one does the same for a whole array of digits to add:

/** * adds all the digits from the addend array to the result array. */ private void addDigits(int[] result, int resultIndex, int... addend) { addendIndex = addend.length - 1; while(addendIndex >= 0) { addDigit(result, resultIndex, addend[addendIndex]); addendIndex--; resultIndex--; } }

Now we can implement our plus method:

/** * calculates the sum of this and that. */ public DecimalBigInt plus(DecimalBigInt that) { int[] result = new int[Math.max(this.digits.length, that.digits.length)+ 1]; addDigits(result, result.length-1, this.digits); addDigits(result, result.length-1, that.digits); // cut of leading zero, if any if(result[0] == 0) { result = Arrays.copyOfRange(result, 1, result.length); } return new DecimalBigInt(result); }

We could do a bit better here if we would look before if overflow is at all possible and only then create the array one bigger than necessary.

Ah, one test: d2.plus(d2) gives Big[24, 691357802, 469135780], which looks right.

Having this, we can also implement multiplication (next part).

If you need to work with big numbers (i.e. anything that is larger than what fits in a long) in Java, you usually would work with java.math.BigInteger.

But did you ever wonder how it works? A Java VM basically can only work with small numbers (i.e. the primitive types int, long, float, double - the other (smaller) ones are represented as int for calculations), everything bigger than that must be composed from these.

Some time ago, a new user frodosama asked this question on Stack Overflow:

How would I go about doing arithmetic, + - / * % !, with arbitrarily large integers without using java.math.BigInteger?

For instance, the factorial of 90 returns 0 in Java. I would like to be able to solve that.

The discussion about the question hinted that normally one would use BigInteger here, but frodosama did not want this. (Maybe it was a homework task where BigInteger was forbidden.)

My own answer started like this:

I think a programmer should have implemented his own bignum-library once, so welcome here.

(Of course, later you'll get that BigInteger is better, and use this, but it is a valuable learning experience.)

Since the answer is quite long, I'll split it over several blog posts here (with minor edits).

You can get the final source code in my github repository.

If you like this, consider voting it up on Stackoverflow, if you already have an account there (and voting rights, which needs 15 reputation).