Investigation: Faster Conversion through Bases

Before reading this, you may want to look over this article on Number Base Representation.

Let's start with a simple problem: Convert $10100111_2$ to base $4$.

We first convert $10100111_2$ to base $10$, then convert that to base $4$, as shown by the Number Base Representation article.

We see that $10100111_2=1+2+4+32+128=167$. Now we convert this into base $4$:

How many times does $4^4=256$ go into $167$? None, we go down to test the next place.

How many times does $4^3=64$ go into $167$? $2$ times. Now we multiply $2$ by $64$ to get $128$, and subtract this from $167$ to get $39$.

How many times does $4^2=16$ go into $39$? Twice, so we multiply $16$ by $2$ to get $32$, and subtract that from $39$ to get $7$.

How many times does $4^1=4$ go into $7$? $1$ time, so we subtract $4$ from $7$ to get $3$.

How many times does $4^0=1$ go into $3$? $3$ times. Finally, our answer is $2213_4$.

Phew, that was a pretty calculation-heavy problem. If only there was an easier way...

Let's look at our original base $2$ number and our base $4$ number more closely: $10100111\iff 2213$. Do you notice anything interesting?

How about if I do this: $10|10|01|11\iff 2|2|1|3$?

We notice that in each little subdivision, the base $2$ representation is automatically converted to the base $4$ representation, independent of anything else! For example, $10_2=2_4$, $01_2=1_4$, and $11_2=3_4$.

Why does this work? Let's observe what is happening, fundamentally: We can represent

$10100111_2=1\times 2^7+0\times 2^6+1\times 2^5+0\times 2^4+$$0\times 2^3+1\times 2^2+1\times 2^1+1\times 2^0$.

Let's see what happens when we group this as follows: $10100111_2=(1\times 2^7+0\times 2^6)+(1\times 2^5+0\times 2^4)+$ $(0\times 2^3+1\times 2^2)+(1\times 2^1+1\times 2^0)$

Now we factor out the common multiple in each box:

$10100111_2=2^6(1\times 2^1+0\times 2^0)+2^4(1\times 2^1+0\times 2^0)+$ $2^2(0\times 2^1+1\times 2^0)+2^0(1\times 2^1+1\times 2^0)$

Simplifying, we get that $10100111_2=2\times 4^3+2\times 4^2+1\times 4^1+3\times 4^0$

But wait a minute! The stuff on the $\text{RHS}$ is exactly what a base $4$ representation looks like! Therefore, we can clearly see that $10100111_2=2213_4$.

Here is the trick in practice: We see that to convert base $2$ to base $4$, we group into groups of 2. So we have $10100111\implies 10|10|01|11$.

We see that $10_2=2_4$, $10_2=2_4$, $01_2=1_4$, and $11_2=3_4$. Therefore our answer is $\boxed{2213_4}$. You can see how much faster this is than to convert to base $10$, then back to base $4$.

It turns out that to convert a base $2$ number to a base $2^x$ number, we group the original number's digits into groups of $x$. I'll prove this later.

How about this problem: Convert $10100111_2$ to base $8$.

Thinking along the lines of our previous exercise, we try to group the digits in $10100111_2$ to get the base representation of a number base $8$.

Seeing that $2^3=8$, let's try groupings of threes.

We try to group $10100111_2$ into groups of threes, but we can't, because there are $8$ digits and $8$ isn't divisible by $3$. What do we do?

Well, we want there to be $9$ digits, so we simply add a $0$ at the beginning and there will be $9$ digits. It won't change the value of the number, so we are safe in doing this.

Now we can group as follows: $10100111_2\implies 010|100|111$.

Writing this out as the definition of a base number, we see that $10100111_2=(0\times 2^8+1\times 2^7+0\times 2^6)+$$(1\times 2^5+0\times 2^4+0\times 2^3)+(1\times 2^2+1\times 2^1+1\times 2^0)$

Factoring out and simplifying, we get that $10100111_2=2\times 2^6+4\times 2^3 + 7\times 2^0$.

Simplifying, we get that $10100111_2=2\times 8^2 + 4\times 8^1+ 7\times 8^0=247_8$ and we are done.

In practice, you won't go through all of these steps. You'll just see:

$10_2=2_8$, so the leftmost digit is $2$.

$100_2=4_8$, so the middle digit is $4$.

$111_2=7_8$, so the last digit is $7$ and our final answer is $247_8$.

This isn't limited to just powers of two; try this problem for yourself: Convert $12002210_3$ to base $9$.

Warning: Intense Math Ahead!

Now we'll prove this cool trick for any arbitrary starting base $b$ converted into base $b^x$ for some positive integer $x$.

Let the starting number be $(d_1d_2\cdots d_{nx})_b$.

We are assuming that there is a multiple of $x$ digits in the number; if this is not the case, add leading $0$'s to the beginning of the number until this is the case.

We represent this number as $d_1b^{nx-1}+d_2b^{nx-2}+\cdots +d_{nx}b^0$.

Now we group the digits into groups of $x$ each: $(d_1b^{nx-1}+\cdots + d_xb^{(n-1)x})+$$(d_{x+1}b^{(n-1)x-1}+\cdots +d_{2x}b^{(n-2)x})+\cdots +$$(d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0)$.

Factoring each group, we get $b^{(n-1)x}(d_1b^{x-1}+\cdots +d_xb^0)+$$b^{(n-2)x}(d_{x+1}b^{x-1}+\cdots +d_{2x}b^0)+\cdots +$$b^0(d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0)$.

Changing $b^{(n-i)x}$ to $(b^x)^{n-i}$ for all $i=1\rightarrow n$, we get that $(d_1d_2\cdots d_{nx})_b=(b^x)^{n-1}(d_1b^{x-1}+\cdots +d_xb^0)+$$(b^x)^{n-2}(d_{x+1}b^{x-1}+\cdots +d_{2x}b^0)+\cdots +$$(b^x)^0(d_{(n-1)x+1}b^{x-1}+\cdots +d_{nx}b^0)$. This is exactly the base representation of a base $b^x$ number, so we are done.

You may think, after reading all of this, that this way of converting bases is way easier; you won't ever need to use the classic convert-to-10-then-to-desired-base trick. However, this is unfortunately not the case. This trick only works for converting a base $b$ number to a base $b^x$ number, i.e this trick will not work for converting a base $6$ number into a base $3$ number. This is because there is not way to group the digits so that one base turns into the other.

However, when in the occasion of changing a base $b$ number to a base $b^x$ number, you will know a neat and fast trick to do so. (These occasions happen frequently in competition math.)

Problems

*1. * Convert $12321_4$ to base $16$.

*2. * Convert $112010032_4$ to base $8$. Hint: do an intermediate conversion first.

*3. * Convert $12345678_9$ to base $3$.

*4. * Prove the formula for converting a base $b^x$ number to a base $b^y$ number.