# How many fractional digits do I need to represent a number of base $m$ in base $n$?

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

-

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

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

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

-
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