1
$\begingroup$

I'm trying to work out a formula that gives me the minimum number of digits required to express a number in a target radix (r2) knowing only the source radix (r1) and number of significant digits (d).

I've been messing around with this for quite some time but I think I've figured out that the formula is:

$\left\lfloor \log_{r2}(r1) × d\right\rfloor + 1$

My question is, did I get this right? It works for a variety of examples, but I know that doesn't necessarily mean it's correct. I lack the skills to prove it. I didn't study advanced math. Please go easy on me.

$\endgroup$
1
$\begingroup$

Let $r_1, r_2 > 1$ be the two bases, then the smallest number requiring $n+1$ digits in base $r_1$ is $r_1^n$ which has representation $10\ldots 0$ (where we have $n$ zeros), therefore an arbitrary number $m$ needs $n+1$ digits if and only if $$ r_1^n \le m < r_1^{n+1} $$ and this relation holds in any base. Also for the same $m$ we have $$ r_2^{n \cdot \log_{r_2} r_1} \le m < r_2^{(n+1) \cdot \log_{r_2} r_1}. $$ So the number of digits needed to represent $m$ in base $r_2$ is contained between $\lfloor n\log_{r_2} r_1 \rfloor + 1, \ldots, \lceil (n+1)\log_{r_2} r_1 \rceil + 1$. So your formula is indeed a good approximation and some times it is right. For example consider $r_1 = 2, r_2 = 3$, and: $$ \begin{array}{l|l|l|l|c|c} m & r_1 & r_2 & d_2 & d_3 & \lfloor (d_2-1)\cdot \log_3 2 \rfloor + 1 & \lceil d_2\cdot \log_3 2\rceil + 1 \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 1 & 1 & 2 \\ 2 & 10 & 2 & 2 & 1 & 1 & 3 \\ 3 & 11 & 10 & 2 & 2 & 1 & 3 \\ 4 & 100 & 11 & 3 & 2 & 2 & 3 \\ 5 & 101 & 12 & 3 & 2 & 2 & 3 \\ 6 & 110 & 100 & 3 & 3 & 2 & 3 \\ 7 & 111 & 101 & 3 & 3 & 2 & 3 \\ \end{array} $$ As you can see in the table, for $m = 3$ the number of digits needed in base $3$ is strictly between the bounds, for $m \in \{0,1,2,4,5\}$ the lower bound is assumed, and for $m \in \{ 6,7 \}$ the upper bound is assumed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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