2.2 Going from Decimal to Other Numbering Systems

Now that you have a working knowledge of the Euclidean algorithm, I think now is a good time to apply this algorithm in the context of BS1009: Introduction to Computational Thinking.

2.2.1 Example #1

Suppose that I wanted to convert the decimal number $51_{10}$ to binary. Here’s what I would do using the Euclidean algorithm; I would first start by dividing 51 by 2. The remainder of that division will be the first, rightmost digit on my converted number:

$$\begin{align*} 51 = 2(25) + 1 \end{align*}$$

Hence, my first digit is going to be a 1. We then repeat the above process until the quotient is too small to be divided further. When this happens, the quotient is then the last digit (from the right) of our converted number:

$$\begin{align*} 25 &= 2(12) + 1 \\ 12 &= 2(6) + 0 \\ 6 &= 2(3) + 0 \\ 3 &= 2(1) + 1 \end{align*}$$

Hence, we see that $51_{10} = 110011_2$ in binary. I can verify this using the material presented in the lecture:

$$\begin{align*} 1\times2^0 + 1\times2^1 + 0\times2^2 + 0\times2^3 + 1\times2^4 + 1\times2^5 &\stackrel{?}{=} 51 \\ 32 + 16 + 2 + 1 &\stackrel{?}{=} 51 \\ 51 &\stackrel{\checkmark}{=} 51 \end{align*}$$

And it works!

2.2.2 Example #2

Now, I want to convert the decimal number $413_{10}$ to hexadecimal. The process still remains the same using the Euclidean algorithm, but instead of dividing by $2$, I will divide by $16$ this time:

$$\begin{align*} 413 &= 16(25) + 13 \\ 25 &= 16(1) + 9 \end{align*}$$

Hence, $413_{10} = 19D_{16}$. Again, I can verify this:

$$\begin{align*} D \times 16^0 + 9 \times 16^1 + 1 \times 16^2 &\stackrel{?}{=} 413 \\ 13 + 144 + 256 &\stackrel{?}{=} 413 \\ 413 &\stackrel{\checkmark}{=} 413 \end{align*}$$

And it also works!