Changing a number between arbitrary bases

Question

As an intro, I know how the numbers are represented, how to do it if I can calculate powers of the base, and then move between base $m$ to base $10$ to base $n$. I feel that this is overly "clunky" though, and would like to do it in such a way that the following conditions are met:

1. No need to calculate the powers of the base explicitly
2. No need for intermediate storage (i.e. no conversion to base ten required if base ten is not one of the bases)

I am pretty sure that the only operations that I strictly need to use are modulo, division and concatenation, but I can't seem to figure it out.

Any pointers?

Answer 1

Let $x$ be a number. Then if $b$ is any base, $x \% b$ ($x$ mod $b$) is the last digit of $x$'s base-$b$ representation. Now integer-divide $x$ by $b$ to amputate the last digit.

Repeat and this procedure yields the digits of $x$ from least significant to most. It begins "little end first."

EDIT: Here is an example to make things clear.

Let $x = 45$ and $b = 3$.

x   x mod 3
45    0
15    0                (integer divide x by 3) 
 5    2
 1    1

We see that $45 = 1200_3$. Read up the last column to get the base-3 expansion you seek. Let us check.

$$1\cdot 3^3 + 2\cdot 3^2 + 0 + 0 = 27 + 18 = 45.$$

I hope this helps you.

Answer 2

You can perform base conversion directly by representing radix notation in horner (nested) form. Let's work a simply example. We convert $\:1213_{\:6}\:$ from radix $6$ to radix $8$

$$ 1{\color{red}2}{\color{blue}1}{\color{orange}3}_{\:6}\ =\ ((1\cdot 6+{\color{red}2})\:6+{\color{blue}1})\:6 + {\color{orange}3}$$

Now perform the computation inside-out in radix $8$:

$$ 1\cdot 6+ {\color{red}2} = 10)\: 6 = 60) + {\color{blue}1}) = 61)\: 6 = 446) + {\color{orange}3} = 451$$

Hence $\:1213_{\:\!6} = 451_{8}$