Converting base of floating point number without losing precision

Question

Terminology

In this question I am calling "floating point number" "decimal number" to prevent ambiguation with the float/double Java primitive data types. The term "decimal" has no relationship with "base 10".

Background

I am expressing a decimal number of any base in this way:

class Decimal{
    int[] digits;
    int exponent;
    int base;
    int signum;
}

which approximately expresses this double value:

public double toDouble(){
    if(signum == 0) return 0d;
    double out = 0d;
    for(int i = digits.length - 1, j = 0; i >= 0; i--, j++){
        out += digits[i] * Math.pow(base, j + exponent);
    }
    return out * signum;
}

I am aware that some conversions are not possible. For example, it is not possible to convert 0.1 (base 3) to base 10, because it is a recurring decimal. Similarly, converting 0.1 (base 9) to base 3 is not possible, but covnerting 0.3 (base 3) is possible. There are probably other cases that I have not considered.

The traditional way

The traditional way (by hand) of change of base, for integers, from base 10 to base 2, is to divide the number by the exponents of 2, and from base 2 to base 10 is to multiply the digits by respective exponents of 2. Changing from base x to base y usually involves converting to base 10 as an intermediate.

First question: Argument validation

Therefore, my first question is, if I were to implement the method public Decimal Decimal.changeBase(int newBase), how can I validate whether newBase can be made without resulting in recurring decimals (which is incompatible with the design of the int[] digits field, since I don't plan to make an int recurringOffset field just for this.

Second question: Implementation

Hence, how to implement this? I instinctively feel that this question is much easier to solve if the first question is solved.

Third question: What about recurring number output:

I don't plan to make an int recurringOffset field just for this.

For the sake of future readers, this question should also be asked.

For example, according to Wolfram|Alpha:

0.1 (base 4) = 0.[2...] (base 9)

How can this be calculated (by hand, if by programming sounds too complicated)?

I think that a data structure like this can represent this decimal number:

class Decimal{
    int[] constDigits;
    int exponent;
    int base;
    int signum;
    @Nullable @NonEmpty int[] appendRecurring;
}

For example, 61/55 can be expressed like this:

{
    constDigits: [1, 1], // 11
    exponent: -1, // 11e-1
    base: 10,
    signum: 1, // positive
    appendRecurring: [0, 9]
}

---

Not a homework question

I am not looking for any libraries. Please do not answer this question with reference to any libraries. (Because I'm writing this class just for fun, OK?)

Answer 1

To your first question: whenever the prime factors of the old base are also among the prime factors of the new base you can always convert without becoming periodic. For example every base 2 number can be represented exactly as base 10. This condition is unfortunately sufficient but not necessary, for example there are some base 10 numbers like 0.5 that can be represented exactly as base 2, although 2 does not have the prime factor 5.

When you write the number as fraction and reduce it to lowest terms it can be represented exactly without a periodic part in base x if and only if the denominator has only prime factors that also appear in x (ignoring exponents of primes).

For example, if your number is 3/25 you can represent this exactly in every base that has a prime factor 5. That is 5, 10, 15, 20, 25, ...

If the number is 4/175, the denominator has prime factors 5 and 7 and therefore can be represented exactly in base 35, 70, 105, 140, 175, ...

For implementation, you can either work in the old base (basically doing divisions) or in the new base (basically doing multiplications). I would avoid going through a third base during the conversion.

Since you added periodic representations to your question the best way for conversion seems to be to convert the original representation to a fraction (this can always be done, also for periodic representations) and then convert this to the new representation by carrying out the division.

Answer 2

To answer the third part of the question, once you have your fraction reduced (and you found out that the "decimal" expansion will be a recurring fraction), you can detect the recurring part by simply doing the long-hand division and remembering the remainders you've encountered.

For example to print out 2/11 in base 6, you do this:

2/11    = 0 (rem 2/11)
2*6/11  = 1 (rem 1/11)
1*6/11  = 0 (rem 6/11)
6*6/11  = 3 (rem 3/11)
3*6/11  = 1 (rem 7/11)
7*6/11  = 3 (rem 9/11)
9*6/11  = 4 (rem 10/11)
10*6/11 = 5 (rem 5/11)
5*6/11  = 2 (rem 8/11)
8*6/11  = 4 (rem 4/11)
4*6/11  = 2 (rem 2/11) <-- We've found a duplicate remainder

(Had 2/11 been convertible to a base 6 number of finite length, we would've reached 0 remainder instead.)

So your result will be 0.[1031345242...]. You can fairly easily design a data structure to hold this, bearing in mind that there could be several digits before the recurrence begins. Your proposed data structure is good for this.

Personally I'd probably just work with fractions, floating point is all about trading in some precision and accuracy for compactness. If you don't want to compromise on precision, floating point is going to cause you a lot of trouble. (Though with careful design you can get pretty far with it.)