Base conversions: issue with fractions

Question

I have written a system that is able to convert any base (2-36) to another base with whole numbers, and it can convert any real number from base 10 to any other base (2-36).

My problem arises with converting a rational/irrational number from any base besides 10 to another base.

I use the following algorithm for right-side of the decimal point conversion:

1) Take the right side of the decimal point (0.xxxxxx--->) in the input and multiply it by the base you are converting to.

2) Take the number greater than one (left of the point) and add it to the right side of the converted number.

3) Take the right side of the product and use it in the next repetition as the multiplier (it times the base)

4) Repeat until satisfied or left with a whole number (0 on the right side).

This works nicely for converting any floating point number from decimal to another base, but obviously you can't convert FROM a base that isn't decimal.

So what I tried is converting that initial value to the right of the decimal to base 10, performing the math part, and then converting it back to the original base for when I add it to the output value (it's converted to the new base before being added).

Unfortunately, this returns incorrect results for the right side of the decimal point. So, I have answers that are always correct on the left side, but incorrect on the right if converting from a base that is not base 10.

Does anyone have any ideas for how to make this work? Or perhaps it just won't?

EDIT

Alternatively, can anyone link me/show me how to convert a rational hexadecimal value into decimal? That alone would be sufficient for me to work around this issue.

SOLUTION

I found a fairly easy workaround to this problem for anyone else in the future who reads this question.

All you have to do is the take the number on the right side of the decimal (whatever base it may be) and convert it to decimal (you can see how to convert integers here). Then take that number and divide it by the greatest place value in it. For instance:

A.C
C == 12 (dec)
12 / 16 = .75 (this is the fractional value in decimal)

You can then take that fractional decimal value and run it through the algorithm I discussed above.

Thanks for everyone's help on this issue!

Answer 1

Using floating point implies that you do not want to perform accurate computation.

Only numbers written in bases 2, 4, 8, 16,... can ever be accurately represented in Java floating point values (leaving integers aside). This is due to the limitations of the floating point representation.

Only numbers written in bases 2, 4, 5, 8, 10, 16, 20, 25, 32,... can be accurately printed in the decimal base. This is due to the limitation of our decimal number system.

I expect that you should therefore adapt some rules as to rounding of results and implement those throughout the algorithm. Make sure that you round rather than truncate, otherwise going through the floating points will give you incorrect results even in cases where the precision of the double type is sufficient for your purposes, or where the number can be accurately represented.

If you want to perform the computation in much higher precision, look at the BigInteger class and redesign your algorithm exclusively in integers. Alternatively, use a library for working with fractions; this is useful because the inputs to your algorithm can always be accurately represented as a fraction. However, in the end it always boils down to defining result rounding rules and implementing them correctly.

Edit:

1. As I learned from the comments, you prefer to emit output digits gradually, before the whole input is read. This is basically possible, but

   • You need to keep an interval, rather than a single number, as the "accummulator"; for example, if you have so far read 0.1111 in ternary, then you know that the output lies between 0.49382716 and 0.50617284 and you cannot emit even the first decimal digit after the decimal point at this stage. This is necessary to avoid seeing outputs like 0.4999999992 on the most "rational" of inputs.

   • When the full input is read, it is safer to "round up" and emit output based on the upper bound of the interval rather than on the bottom bound. This way 0.1111 in ternary will be converted to 0.5 in decimal. (This can be ignored if you are limited to hex to decimal conversion.)

   • Keep track of the maximum precision achieved by the input (logarithm of the width of the interval) and make sure you emit no more output digits than the input guarantees.

   • Use an internal representation of interval endpoints (lower and upper bounds) that can safely deal with the maximum precision you need.

   • Keep in mind that even quite popular software occasionally gets the details of this algorithm wrong and stay away from representing any intermediate results in floating point data types, or truncate the input to a number of digits that they can safely represent if it is longer.

2. You mention irrational numbers in the question, but every number that can be expressed with a finite (or periodically repeating) expansion, regardless of the base used, is necessary a rational number.

3. In conversions from hex to decimal, the output can even always be represented accurately which allows some simplifications like indefinitely waiting for the lower and upper bound to converge.