# Efficient base conversion with limited precision

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?

-

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$.

-
After Raymond's comment, I'm wondering whether I correctly interpreted your intention. This calculates the result correctly rounded to two decimal digits. If you want the result truncated to two decimal digits, you can multiply by $100$ and take the integer part instead; and if you're not interested in exact rounding or truncation and just want something that's within $10^{-2}$ of the number, Raymond's answer gets you close enough. –  joriki Apr 22 '12 at 13:20
Thank you, in fact I was implicitly assuming that the result should be correctly rounded. You gave me the suggestion I was looking for, I just changed it a little bit for my purpose: I multiply by 100 from the left until the difference from the next half integer exceeds what the remaining digits would contribute if they all had the maximum value possible in that base. Then I round up or down to whichever integer is next, convert to base 10 and insert the decimal point just before the second digit from the right. –  GOTO 0 Apr 22 '12 at 14:49
@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. –  joriki Apr 25 '12 at 11:12

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!

-
This isn't guaranteed to give the right result to two decimal digits precision. The number of ternary digits required to reach two decimal digits precision can be arbitrarily large. For instance, the ternary expansion of $.5_{10}$ is $.111111\ldots_3$, and you'll never know from looking at finitely many digits whether this is above or below $.5_{10}$. –  joriki Apr 22 '12 at 12:18
@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!) –  Raymond Manzoni Apr 22 '12 at 12:35