Now we have the basics to convert to an arbitrary radix. Of course, not really arbitrary, only radixes smaller than `RADIX` are allowed, but this should not be a too big problem.

As explained in part 10, we have to do division, remainder, multiply, add. The “multiply-add” part is in fact only putting together the individual digits, so we can replace it by a simple array-access.

As we always have to use both the quotient and the remainder, we won’t use the public methods `modulo` and `divideBy`, but instead repeatedly call the `divideDigits` method.

``````/**
* converts this number to an arbitrary radix.
* @return the digits of this number in the base-radix system,
*     in big-endian order.
*/
{
" out of range!");
}
``````

First, a special-case handling for 0.

``````    // zero has no digits.
if(digits.length == 0)
return new int[0];
``````

Then, we create an array for the result digits (long enough), and some other variables.

``````    // raw estimation how many output digits we will need.
// This is just enough in cases like RADIX-1, and up to
// 30 digits (for base 2) too much for something like (1,0,0).
int[] rDigits = new int[len];
int rIndex = len-1;
int[] current = digits;
int quotLen = digits.length;
``````

`quotLen` is the number of digits (excluding leading zeroes) in the last quotient. If this is 0, we are done.

``````    while(quotLen > 0)  {
``````

A new array for the next quotient.

``````        int[] quot = new int[quotLen];
``````

The quotient-and-remainder operation. The quotient is now in `quot`, the remainder in `rem`.

``````        int rem = divideDigits(quot, 0,
current, current.length - quotLen,
``````

We put the remainder in the output array (filling it from the last digit).

``````        rDigits[rIndex] = rem;
rIndex --;
``````

Then we swap the arrays for the next round.

``````        current = quot;
``````

If there are leading zeros in the quotient (there will be at most one, since radix is smaller than RADIX), we shrink the quotient size by one. The next array will be smaller.

``````        if(current[0] == 0) {
// omit leading zeros in next round.
quotLen--;
}
}
``````

After the loop there may be leading zeros in the rDigits array, and we cut them off.

``````    // cut of leading zeros in rDigits:
while(rIndex < 0 || rDigits[rIndex] == 0) {
rIndex++;
}
return Arrays.copyOfRange(rDigits, rIndex, rDigits.length);
}
``````

That’s it. It looks a bit complicated, though. Here is an example of how to use it:

``````    System.out.println("d4 in base 11: " +
Arrays.toString(d4.convertTo(11)));
System.out.println("d5 in base 7: " +
Arrays.toString(d5.convertTo(7)));
``````

These print `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]` and `[1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0]`, just the same numbers as we parsed before (from a String, though).

Based on this we can also format as a string:

``````/**
* Converts the number to a String in a given radix.
* This uses {@link Character.digit} to convert each digit
* to one character.
* @return a String containing the digits of this number in the
*   specified radix, using '0' .. '9' and 'a' .. 'z' (as much as needed).
*/
}
if(digits.length == 0)
return "0";
StringBuilder b = new StringBuilder(rdigits.length);
for(int dig : rdigits) {
}
return b.toString();
}
``````

We now apply the theory from part 10 to our case, first for conversion from an arbitrary radix to our format (the other direction requires division and remainder, which we don’t yet have).

(The radix is not totally arbitrary: only radixes smaller than RADIX are allowed. But this should not really be a problem, as our RADIX is quite huge. And if the other radix is a power of some number smaller than RADIX, we can easily convert the number first to this smaller radix, before converting.)

Basically we use the Horner scheme to calculate the value of polynomial with the digits as coefficients at the point given by the radix.

``````sum[i=0..n] digit[i] * radix^i
``````

can be calculated with this loop:

``````value = 0;
for  i = n .. 0
value = value * radix + digit[i]
return value
``````

Since our input arrays are big-endian, we don’t have to count down, but can use a simple enhanced for loop. (It looks more ugly in Java, since we have no operator overloading, and no autoboxing from int to our DecimalBigInt type. Also, we put in the argument checking.)

``````/**
* creates a DecimalBigInt from a representation
*
* @param digits the individual digits, each between 0 (inclusive)
* @param radix the radix of the representation, an arbitrary value >= 2.
*    (Base-1 representations are not allowed.)
*/
public static DecimalBigInt valueOf(int[] digits, int radix) {
}
DecimalBigInt value = ZERO;
for(int digit : digits) {
if(digit < 0 || radix <= digit) {
throw new IllegalArgumentException("digit " + digit +
" out of range");
}
DecimalBigInt bigDigit = DecimalBigInt.valueOf(digit);
}
return value;
}
``````

In the more usual case, the input is not an `int[]`, but instead a String. We provide a second version of our method, for radixes up to 36 (which is the supported range of Character.digit):

``````/**
* creates a DecimalBigInt from a string-representation
*
* Note: this is not the most efficient implementation, since we
* use the Horner scheme on DecimalBigInt values, instead working
* directly on {@code int[]} and convert to a DecimalBigInt only
* in the end.
*
* @param text the big-endian string representation of the number, using
*  the decimal digits '0' ... '9' and additionally the latin
*  letters 'A' ... 'Z' (or 'a' ... 'z'). (Only letters below
*  the given radix are allowed, of course.)
*/
public static DecimalBigInt valueOf(String text, int radix) {
}
DecimalBigInt value = ZERO;
for(char digit : text.toCharArray()) {
if(iDigit < 0) {
throw new NumberFormatException("digit " + digit +
" is not a valid base-"+radix+
"-digit.");
}
DecimalBigInt bigDigit = new DecimalBigInt(iDigit);
}
return value;
}
``````

Converting to an arbitrary positional system is more complicated, as it involves remainder and division (by the arbitrary radix), which we did not implement yet - so not for now. It will be done when I have a good idea on how to do division. (We need only division by small (one-digit) numbers here, which may be easier than a general division.)

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?

1. Take the remainder modulo 3 - prepend this digit to the result.
2. Divide by 3.
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.

### Big numbers selfmade: Part 1/14: Number Representation

First, we need a representation of the number, based on the data types Java gives us.

As the asker thought the decimal conversion is the most complicated part, let’s stay in a decimal based mode. For efficiency, we’ll store not single decimal digits, but work in radix (or base) `1 000 000 000 = 10^9 < 2^30` (This is one billion in US English, in German it is eine Milliarde, while eine Billion is 10^12 here. As the exact value does not really matter for most of the calculations here, I’ll most often simply speak about radix). This nicely fits in a Java `int` (up to `2^31` or `2^32`), and the product of two such digits fits nicely in a Java `long`.

``````final static int RADIX = 1000000000;
final static int RADIX_DECIMAL_DIGITS = 9;
``````

Then the digits-array:

``````private int[] digits;
``````

Do we store the digits in little or big endian format, i.e. the most significant digits last or first? It does not really matter, so we decide on big endian since this is how humans want to read it. (We will later see that little endian format would have made some of the implementations prettier. If you do this again, try it with little endian.)

For now we concentrate on non-negative values - later we can add a sign bit for negative numbers.

For testing purposes, we add a constructor which allows initializing from such a `int[]`.

``````/**
* creates a DecimalBigInt based on an array of digits.
* @param digits a list of digits, each between 0 (inclusive)
* @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();
}
``````

As a added bonus, this constructor is also usable for a single `int` (if smaller than `RADIX`), and even for no `int` (which we’ll interpret as 0). So, we now can do this:

``````DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345);
System.out.println(d);
``````

This gives us `de.fencing_game.paul.examples.DecimalBigInt@6af62373`, not so useful. So, we add a `toString()` method:

``````/**
* A simple string view for debugging purposes.
* (Will be replaced later with a real decimal conversion.)
*/
public String toString() {
return "Big" + Arrays.toString(digits);
}
``````

The output is now `Big[7, 5, 2, 12345]`, which is more useful for testing, isn’t it?