2
$\begingroup$

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  

3 Answers 3

3

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

  • 0
    I've updated my question with example code base on the prime factorisation expression in your answer. I would be grateful if you could take a quick look to review it. The code you gave only produces a value for _d_ if an exact representation is always possible between _m_ and _n_.2012-12-18
2

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.

  • 0
    @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.2012-12-15
1

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.

  • 0
    @EricStucky: I hadn't considered that. I'll try to bear that in mind in the future. Thanks!2012-12-18