Pensoj de Paŭlo

Big numbers selfmade: Part 13/14: Conversion to arbitrary radix

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.
 * @param radix the target radix, {@code 1 < radix < RADIX}.
 * @return the digits of this number in the base-radix system,
 *     in big-endian order.
 */
public int[] convertTo(int radix)
{
    if(radix <= 1 || RADIX <= radix) {
        throw new IllegalArgumentException("radix " + radix +
                                           " 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 len = (int) (Math.log(RADIX) / Math.log(radix) * digits.length)+1;
    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,
                               radix);

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.
 * @param radix the radix to use, between {@link Character.MIN_RADIX}
 *   and {@link Character.MAX_RADIX}.
 * @return a String containing the digits of this number in the
 *   specified radix, using '0' .. '9' and 'a' .. 'z' (as much as needed).
 */
public String toString(int radix) {
    if(radix < Character.MIN_RADIX || Character.MAX_RADIX < radix) {
        throw new IllegalArgumentException("radix out of range: " + radix);
    }
    if(digits.length == 0)
        return "0";
    int[] rdigits = convertTo(radix);
    StringBuilder b = new StringBuilder(rdigits.length);
    for(int dig : rdigits) {
        b.append(Character.forDigit(dig, radix));
    }
    return b.toString();
}

---

0: introduction, 1: number representation, 2: conversion from decimal format, 3: decimal formatting, 4: addition, 5: multiplication, 6: factorials, 7: comparison, 8: normalizing, 9: equals/hashCode, 10: converting between arbitrary radix systems, 11: converting from arbitrary radix, 12: division by small numbers, 13: conversion to arbitrary radix, 14: missing bits - Original question - Full code