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

Does anyone know of an algorithm or formula for converting between and arbitrary base $n$ to another base $m$?

-
Reason for downvote: at least you could have tried. This is fairly straightforward. (And if you did try - please let us know what you did try and I'll remove the -1.) –  M.B. Jul 2 '11 at 2:22
@M. B. Thanks for explaining the downvote. Since computers store in binary and both Python and Mathematica (among others) will render numbers in any base you want... –  Ross Millikan Jul 2 '11 at 3:50

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.

-
Im not mathmatician, actually quity bad at it, but i need a quick algorithm form pasing from base 16 to 1024 or 256. ps I have allready checked wikipedia –  fernando Jul 6 '11 at 23:57
@fernando: ok: I'll edit my answer to include a couple of examples. Check back in a bit. –  mixedmath Jul 7 '11 at 2:18
@fernando: ok, it is done! –  mixedmath Jul 7 '11 at 4:09
Note also that it is easy to check, as 7*1024 = 7168. 7168 + 46 = 7214. And this was the number. Aha! –  mixedmath Jul 7 '11 at 4:10
I would suggest rephrasing "it is pretty easy to work with base 10 by hand" to "most of us are used to working in base 10 by hand" - it's not inherently any harder than other bases, it's just what people are used to. –  Darael Jul 5 '12 at 16:45

To be honest the best way would be to just convert into base 10. Then subtract successive powers of the new base.

For example: 624_7 = 6*49 + 2*7 + 4 = 294 + 14 + 4 = 312 - 256 = 56 - 3*16 = 8

Therefore 624_7 = 138_16.

-

Considering radix notation in nested Horner form leads to an obvious recursive algorithm on the digit list $\rm\: [d_0,d_1,\cdots,d_k]\:$ of $\rm\: d_0 + n\:(d_1 + n\:(d_2 + \cdots + d_k))\:$ in radix $\rm\:n\:.\:$ Namely, 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\:$ and 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.

-
+1 for a different answer, great that you pointing out about m=n^k, it's hard for me to 'translate'your notation into code, but I will google for Horner form. Do you know any paper or related material on this kind of conversion? (I've asked a question about this fact here cs.stackexchange.com/questions/21736/…) –  Hernán Eche Feb 21 '14 at 2:23