2

I'm looking for a general method of radix conversion, that might be performed without using decimal system at all.

Given a number $x$ in base $b_1$, and I want to convert it to the base $b_2$, where $x, b_1, b_2$ are positive integers and $b_1, b2 \ne 10$.

I know the question is very basic but unfortunately, all I have encountered till now were cases where one of the bases is 10, or the conversion method includes decimal system as a step. Also, I found some shortcut methods to convert between certain systems (where both bases are powers of $2$), but is there a general method? Do I miss something and there's a way to achieve it using Euclidean division or Horner's scheme?

Elena
  • 117

2 Answers2

3

In general, there aren't going to be many shortcuts. If you have a number $x$ and you want to express it in base $b$, you perform repeated division by $b$ and take the remainders. If you know the base $b_1$ expansion of $x$ and you want to convert it to base $b_2$, then you're still repeating this process, but your divisions are going to be expressed in base $b_1$ rather than base 10 - which is tough to do by hand if you haven't memorised your $b_2$ times tables in base $b_1$, hence why a lot of examples will translate to base 10 for ease of understanding.

For example, say $x = 301_5$ and we want to convert into base 6 - or base $11_5$, as it were. Then (noting that all of the below is implicitly happening in base 5):

$$\begin{eqnarray} 301 & = & 22 \times 11 + 4 \\ 22 & = & \phantom{0} 2 \times 11 + 0 \\ \phantom{0} 2 & = & \phantom{0} 0 \times 11 + 2 \end{eqnarray}$$

So $301_5 = 204_6$. We can confirm that by converting both into base 10 and seeing that they equal 76, but nowhere in the calculations above did I need to do so.

ConMan
  • 24,300
1

I've just realized I can use the formula $\large x_{b_1} = \displaystyle\sum_{k=n-1}^{0}d_kb_1^k$, where $n$ is number of digits in $x_{b_1}$, $d_k$ is current digit. I knew it as one of the ways to convert a number to the decimal system, but it works for conversion to other integer-based systems as well. Summation should be performed in the target base $b_2$. The situation when $b_2=10$ is just a special case.

Taking the example from @ConMan's answer $$301_5 = 3\cdot 5^2 + 0 \cdot 5^1 + 1 \cdot 5^0 = 203_6 + 1 = 204_6$$ For me it's easier than repetitive division. Besides, the fact that $b^1 =10_b, b^2 = 100_b, b^3=1000_b...$ for any $b \in Z, b>1$ helps with computations.

Elena
  • 117