1
$\begingroup$

I know how to convert the fractional part of a number to a different radix, but I wonder if there is a way to do it more efficiently when only a limited amount of significant digits after the radix point is required in the result.

Suppose you have a number in base, say, 3, with a lot of digits after the radix point.

0.1221020012021220012110221021020102011112... 

I would like to convert that number to base 10, but I'm only interested in the first two digits after the decimal point, so I'm going to use only a few digits in the base 3 operand and ignore the rest. But how many digits do I need to consider exactly in a general case? Is there a special algorithm for a base conversion with limited precision?

2 Answers 2

0

I would convert $200$ to base $3$ (yielding $21102_3$), start multiplying at the left and stop once the distance of the result to the nearest odd integer is greater than what the remaining digits might contribute, convert the integer part to base $10$, add $1$ if the result is odd and divide by $200$.

  • 0
    @ft1: Yes, that was actually the first version of my answer; I just thought that checking the distance from the nearest odd integer would be easier than checking the distance from the nearest half integer.2012-04-25
0

Well n digits in base $b$ represent $d=n\cdot\log_{10}(b)$ digits in base $10$ so that you'll need at least $\dfrac{d}{\log_{10}(b)}$ digits in base $b$ to get $d$ digits in base $10$.

EDIT: Practically take at least $\displaystyle \left\lceil \dfrac{d+\log_{10}(2)}{\log_{10}(b)}\right\rceil$ base $b$ digits (the 'ceil' of the fraction) because we want an error smaller than $\frac 12$ on the next digit.

In your example $d=2,\ b=3$ so that you'll need at least $5$ base $3$ digits
(since $\dfrac{2+\log_{10}(2)}{\log_{10}(3)}\approx 4.8$).

Round the result obtained to $d$ digits (the real result is usually higher since the input is truncated). If you want $d$ exact digits then see Joriki's answer!

  • 0
    @joriki: yes of course and that's why I proposed to round the result (I didn't suppose that the OP wanted $d$ exact digits but $d$ precision digits!)2012-04-22