How to change from base $n$ to $m$

Solution 1:

This is often called "Base Conversion" or "Changing Base." You can read up on it here and here. And anyone who supports the New Math program would probably feel suddenly reinvigorated by this question. ;p

By the way, as it is pretty easy to work with base 10 by hand, I almost suspect that most such algorithms would convert first to base 10 (not so bad, just multiply it out) and then convert to the new base now that division is done base 10 (just divide out different powers of the new base to get the new representation).

------EDIT--------

Ok, let's do a couple of examples that you can use to extract an algorithm. Fortunately, converting from 16 to 256 or 1024 is actually incredibly easy. Really, super easy. But I'll do a general conversion and then a desired one.

I will use the $( \cdot )_b$ notation to mean that the number $ \cdot$ in base b.

So suppose we have the Hex number $(1C2E)_{16}$ and we want to convert this to base 256. One way to do this is to convert first to decimal. So we do: $$(1C2E)_{16} = 14 + 2 \cdot 16 + 12 \cdot 16^2 + 1 \cdot 16^3 = (7214)_{10}$$ Now that we have it in decimal, we can throw it in base 256 by dividing. $$\lfloor7214/256 \rfloor= 28 \quad ;\quad 7214 \mod {256} = 46$$ So our number written in base 256 is $(28,46)_{256}$, where 28 means whatever symbol we use for 28 and 46 is the symbol for 46, just like we use A for 10 in Hex. The comma separates the positions.

The fortunate part about this conversion though is that $16^2 = 256$. So we can just look at our Hex notation in blocks of 2 digits, and convert them. This is great! So $1C2E$ can be broken into $1C$ and $2E$. Well, $2E = 2*16 + 14 = 46$ and $1C = 1*16 + 12 = 28$. 28 and 46 again! So the base 256 one is just written as 28,46!

Writing this in base 1024 is more annoying. I recommend that you convert it to base 10 and then to base 1024 using the algorithm suggested above. If you are courageous, you can do it much quicker by converting to binary and then converting from binary. Why is this good? As base 16 is a power of 2, and 1024 is a power of 2, the binary representations don't 'bleed,' i.e. blocks of digits can be considered without worrying about their neighbors.

For example, 1 in binary is 1. C is 8 + 4, and so it 1100. 2 is 10. E is C + 2, so it is 1110. So $(1C2E)_{16}=(1110000101110)_2$. To convert to base 256, since $2^8 = 256$, you just take 8 digits at a time. The last 8 digits are 00101110, and this is 46. The others are 11100, which is 28. That's handy, and done very, very quickly on a computer.

Noting that $2^{10} = 1024$, we can take 10 digit sections of the binary representation to write it in base. The last 10 digits are, astoundingly enough, 0000101110. This still happens to be 46, due to a funny choice of my number. The next 10 digits are 111, which is 7. So in base 1024, it's written as $(7,46)_{1024}$.

That's all there is to be written.

Solution 2:

One sraightforward way it to write the number in (nested) Horner polynomial form then do the base conversion as an "evaluation" into the target radix, e.g. let's convert $397$ from radix $10$ into radix $\color{#c00}9,\,$ where $\rm\color{#c00}{red}$ numbers are in radix $\color{#c00}9$

$$\begin{align} 397 \,&=\, (3\cdot 10\, +\, 9)\,10 +7\\ &=\, (\color{#c00}{3\cdot 11+10})10+7,\ \ {\rm by}\ \ 10_{10} = \color{#c00}{11}_9,\ 9_{10} = \color{#c00}{10}_9\\ &=\qquad\quad\ \ \color{#c00}{43\cdot 11}+7\\ &=\qquad\qquad\ \ \ \color{#c00}{473}+7\\ &=\qquad\qquad\ \ \ \color{#c00}{481}\end{align}$$

This yields an obvious recursive algorithm: for a digit list $\rm\: [d_0,d_1,\cdots,d_k]\:$ denoting $\rm\: d_0 + n\:(d_1 + n\:(d_2 + \cdots + d_k))\:$ in radix $\rm\:n,\,$ recursively compute the radix $\rm\:m\:$ representation of the tail $\rm\:[d_1,d_2,\cdots,d_k],\:$ then, employing radix $\rm\:m\:$ operations, multiply it by $\rm\:n\:$ then add $\rm\:d_0,\:$ after converting both to radix $\rm\:m\:.\:$ Said more succinctly

$$\rm [d_0,d_1,\cdots,d_k]^{(n\ \mapsto\ m)}\ =\:\ d_0^{(n\ \mapsto\ m)}\ +\ n^{(n\ \mapsto\ m)}\ *\ [d_1,d_2,\cdots, d_k]^{(n\ \mapsto\ m)}$$

Unwinding this recursion, it amounts to applying the conversion operation $\rm\:(\ \ )^{\ (n\ \mapsto\ m)}\:$ to all terms in the fully expanded Horner form given above. Note that this conversion map commutes with $+$ and $*$ because it is a ring isomorphism from the integers represented in radix $\rm\:n\:$ to the integers represented in radix $\rm\:m\:$. One is essentially using this isomorphism to transport structure between the rings - here the structure being the polynomial form that is implicit in radix representation.

Various optimizations are possible. For example, for fixed $\rm\:n > m\:$ one can precompute a table mapping the digits in radix $\rm\:n\:$ to their radix $\rm\:m\:$ conversions. Note also that if $\rm\: m = n^k\:$ then the conversion is trivially achieved by partitioning into chunks of $\rm\:k\:$ digits.