Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 0 down vote accepted

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

share|improve this answer
    
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
add comment

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!

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.