Big numbers selfmade: Part 11/14: converting from arbitrary radix
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
* in some arbitrary radix.
*
* @param digits the individual digits, each between 0 (inclusive)
* and radix, exclusive.
* @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) {
if(radix < 2) {
throw new IllegalArgumentException("illegal radix: " + radix);
}
DecimalBigInt bigRadix = valueOf(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);
value = value.times(bigRadix).plus(bigDigit);
}
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
* in some arbitrary radix.
*
* 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.)
* @param radix the radix used in the representation, between
* {@link Character#MIN_RADIX} (2, inclusive) and
* {@link Character#MAX_RADIX} (36, inclusive).
*/
public static DecimalBigInt valueOf(String text, int radix) {
if(radix < Character.MIN_RADIX || Character.MAX_RADIX < radix) {
throw new IllegalArgumentException("radix out of range: " + radix);
}
DecimalBigInt bigRadix = new DecimalBigInt(radix);
DecimalBigInt value = ZERO;
for(char digit : text.toCharArray()) {
int iDigit = Character.digit(digit, radix);
if(iDigit < 0) {
throw new NumberFormatException("digit " + digit +
" is not a valid base-"+radix+
"-digit.");
}
DecimalBigInt bigDigit = new DecimalBigInt(iDigit);
value = value.times(bigRadix).plus(bigDigit);
}
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.)
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
