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 have authored a web application RADIX, which for further optimisation needs to calculate the maximum number of places necessary to precisely represent the fraction part of a number of base $m$ in base $n$ (assuming a precise conversion is possible).

For example, assuming $f$ represents $15$ in base $64$, how many fraction digits are required to represent the number $f.f$ in base $10$?

I know that the maximum number of digits needed to represent the integer part can be calculated by taking the ceiling of $\log_{10}(64)$ * the number of digits (correct me if I'm wrong), but what about the fractional part of the number?

$f.f$ is $15.234375$ in base $10$, so one fraction numeral in base $64$ seems to require up to $6$ fraction digits in base $10$ to represent it, but is there a way I can calculate that in advance for any two bases?

At the moment I am using $\log_2(m)$ * the number of fraction digits of the number in base m, which happens to give just the right answer for the example above, i.e. $\log_2(64)$ is $6$, but it causes me to calculate to an unnecessarily high number of places for other conversions.

Update:

Example code, based on ShreevatsaR's expression for d in terms of m and n using prime factorisation.

# assumes float division    
m = 288    # base of the number to be converted    
n = 270    # base the number is to be converted to   
i = 2
d = 0

while m > 1 and n > 1:
    e = 0
    f = 0

    while m % i == 0:
        e += 1
        m /= i

    while n % i == 0:
        f += 1
        n /= i

    # if i is a prime factor of both m and n  
    if e != 0 and f != 0 and e / f > d:
        d = math.ceil( e / f )                     
    i += 1

if d == 0:
    # No fraction part of a number of base m has a finite
    # representation when converted to base n, and vice versa
else:
    # A maximum of d * r fraction digits is needed to represent the
    # fraction part of a number of base m in base n, where r is the
    # number of fraction digits of the number in base m 
share|improve this question

3 Answers 3

up vote 3 down vote accepted

This is an elaboration of Ross Millikan's answer.

  • First we'll answer the question: to represent a fraction in base $n$, how many digits are needed (after the decimal point)?

If a fraction can be written in base $n$ with $d$ digits afer the decimal point, then it means that it can be written as $a/n^d$, for some integer $a$. (For instance, the fraction $975/64$ can be written as $15.234375 = \frac{15234375}{1000000}$.) Thus, if the fraction is $p/q$ in lowest terms, then the fact that $a/n^d$ is $p/q$ in lowest terms means that $q$ divides $n^d$.
Conversely, if $q$ divides $n^d$, then $p/q = a/n^d$ for some $a$ (to be precise, $a = pn^d/q$), and so the fraction can be written in base $n$ with $d$ digits after the decimal point.

So the number of digits $d$ needed after the decimal point is the smallest $d$ for which $n^d$ is divisible by $q$.


  • Second, to answer the question: when a number written in base $m$ with 1 digit after the decimal point is reduced to fraction $p/q$ in lowest terms, what are the possible values of $q$?

If a number $x$ is written in base $m$ as $x = a.b$ where $a$ is any integer (has any number of digits) and $b$ is a single digit in base $m$, then $x = a + b/m = (ma+b)/m$. So when reduced to lowest terms $p/q$ (which we do by cancelling common factors from $(ma+b)$ and $m$) it must be the case that $q$ is a divisor of $m$.
And in fact it can happen that $q=m$, e.g. when $b = 1$, or $b = q-1$ or more generally $\gcd(b,m) = 1$. (This is because any common factor of $(ma+b)$ and $m$ must also divide $b$, so if $\gcd(b,m) = 1$ then the only common factor is $1$, so we cannot reduce the fraction $(ma+b)/m$ further.)

Similarly, if a number is written in base $m$ with $r$ digits after the decimal point, then when it is reduced to lowest terms, the denominator could be up to $m^r$.


Putting them together, if a number is written in base $m$ with one digit (respectively $r$ digits) after the decimal point, then the number of digits needed after the decimal point to write it in base $n$ is at most the smallest $d$ for which $n^d$ is divisible by $m$ (respectively $m^r$).

Examples:

  • If you use "f" to represent $15$, then "f.ff" in base $64$ represents $15 + (15\times64 + 15)/64^2$, so $q = 64^2$. If you want to now write this in base $10$, then the smallest $d$ for which $10^d$ is divisible by $64^2$ is $d = 12$, so that's how many digits you need. (And indeed, "f.ff" is $15.238037109375$.)

  • If further $c$ represents $12$, then "f.c" represents $15 + 12/64 = 15 + 3/16$, so $q = 16$. Now $10^4$ is divisible by $16$, so you only need $4$ digits for this particular number ($15.1875$).


To actually calculate the smallest $d$ for which $n^d$ is divisible by $m$, the simplest algorithm is to keep trying successive $d$ until one works (you will never need more than $m$ tries). (You could do a binary search over $d$, but this is overkill unless your $m$ and $n$ are, say, over $10000$ and your program is slow because of this pre-computation step.)

You can do a couple of optimizations:

  • If you already know that $m$ is a power of $n$ (e.g. going from base $64$ to base $2$) then $d = \log_{n}m$.
  • When calculating powers of $n$, you can reduce the number modulo $m$ at each step. Something like

     N = n
     d = 1
     while N % m > 0:
       d += 1
       N *= n
       N %= m
       if d > m:
         # exit with error
     return d
    

If you insist on an expression for $d$ in terms of $m$ and $n$ (beyond $\min\left\{d\colon m|n^d\right\}$ say), then we must look at the prime factorisation of $m$ and $n$. If $m$ has prime factorization $p_1^{e_1}p_2^{e_2}\dots$ and $n$ has prime factorization $p_1^{f_1}p_2^{f_2}\dots q_1^{g_1} \dots$ (all the same primes $p_1, p_2 \dots$, plus other primes $q_1, q_2 \dots$), then $$d = \max(\left\lceil\frac{e_1}{f_1}\right\rceil, \left\lceil\frac{e_2}{f_2}\right\rceil, \dots)$$ For example with $m = 288 = 2^5 3^2$ and $n = 270 = 2^1 3^3 5^1$, we have $d = \max(\lceil\frac51\rceil, \lceil\frac23\rceil) = 5$.

share|improve this answer
    
Thank you for this very clear and comprehensive answer. I'll experiment to see if the cost of calculating d is worth it. –  MikeM Dec 15 '12 at 20:13
    
The above algorithm works fine but is unusable with more than a handful of fraction digits because the value of $m^r$ quickly exceeds floating-point accuracy. Is it the case though that I can use it instead just to efficiently determine whether any number in base m can be exactly represented in base n? –  MikeM Dec 17 '12 at 11:41
    
@MikeM: I think you mean powers of $n$, not $m$, and the solution to overflow is already mentioned above: when calculating powers of $n$, reduce mod $m$ at each step (see the Python code above). (And for a given number in base $m$, you write it as a fraction $p/q$, reduced to lowest terms, and calculate powers of $n$ modulo $q$ instead of mod $m$.) –  ShreevatsaR Dec 17 '12 at 11:46
    
I was thinking that the algorithm you gave finds d of n for a single digit of base m, and that I could substitute $m^r$ for m to find d for r digits... I am unable to write the fraction parts as fractions reduced to lowest terms as I'm working with arbitrary-precision values and the cost of doing that would defeat the purpose... I would still like to know whether the algorithm is an efficient way to determine whether a base m number can be exactly represented in base n at all, i.e. if d > m return false. –  MikeM Dec 17 '12 at 12:08
    
@MikeM: Ah I see. Well you can do the calculation (find the number of digits needed in base $n$) for 1 digit in base $m$, and then simply multiply by the number of digits — that will be an upper bound, and not off by much. Also, exact representation is possible for many digits if and only if it's possible for 1 digit. –  ShreevatsaR Dec 17 '12 at 13:14

As Cameron Buie has said, you may have a number that terminates in one base and does not terminate in the other. Assuming it does terminate, represent the fraction as $\frac pq$ in lowest terms. The number of decimals in base $b$ is the smallest power of $b^n$ that can be divided evenly by $q$. So in base $10$, if $q=32=2^5$, you need $5$ decimals to represent it exactly. In base $4$, you would need three places beyond the point. Note that we don't need base information from where we are coming from, just where we are going.

share|improve this answer
    
I can't quite follow your reasoning above, but, regardless, the base from where we are coming from has got to be taken into account. For example, converting from base 4096 to base 2 each fraction numeral may require up to 12 base 2 digits, while going the other way only one digit is required. –  MikeM Dec 15 '12 at 10:33
    
@MikeM: The base you are coming from is accounted for by the $q$. If you are already given the number as a fraction $p/q$ in lowest terms, then only the value of $q$ (as an integer, nevermind the base) matters, not the base you started with. –  ShreevatsaR Dec 15 '12 at 12:01
    
@MikeM: I'd advise you to read this answer more carefully, since it does fully answer your question. The mention of "base 10" is in an example about going from base 10 to 2 (and even there, just to clarify what "32" means). To give another example: when going from base 64 to base 10 (as in your question), the number "f.f" can be written in lowest terms as $15 + 15/64 = 975/64$, hence $q = 64$ and the smallest power of $10$ divisible by $64$ is $10^6$ (the smallest $k$ for which $q$ divides $b^k$ is $6$), so you need $6$ decimal digits. –  ShreevatsaR Dec 15 '12 at 13:36
    
@MikeM: Similarly, if you want to convert some "a.b" in base $m$ to base $n$, then in the worst case $q = m$, so the answer is the smallest power of $n$ divisible by $m$. If you want to convert $a.bc$ (written in base $m$) into base $n$, then in the worst case $q = m^2$, so the answer is the smallest $k$ for which $n^k$ is divisible by $m^2$. Etc. –  ShreevatsaR Dec 15 '12 at 13:37
    
@ShreevatsaR. Thank you for your further explanation. I now understand Ross's answer. Please write your own answer to this question and I will accept it. If possible please write k as a function of m and n (assuming m = q) and include any advice you may have as regards an algorithm. –  MikeM Dec 15 '12 at 16:30

I doubt there is a nice formula for it. For example, $\frac43$ in base $3$ is $1.1$, but in base $2$ it's $1.\overline{01}$, so we go from finitely many fractional digits to infinitely many.

share|improve this answer
    
Perhaps this is more a comment than an answer, Cameron; I've already stated 'assuming a precise conversion is possible'. –  MikeM Dec 15 '12 at 10:26
    
I noticed that, yes. Apparently, I use a different definition of "precise" than you do--namely, "not approximate". Do you mean "finite" instead? –  Cameron Buie Dec 15 '12 at 13:51
    
@Cameron Buie: Generally when dealing with computery things, "precise" and "finite" are equivalent, because computers don't play nicely with infinities. –  Eric Stucky Dec 18 '12 at 12:34
    
@EricStucky: I hadn't considered that. I'll try to bear that in mind in the future. Thanks! –  Cameron Buie Dec 18 '12 at 16:34

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.