How the decimal to binary convertion algorithm works?

Introduction

 

Do you remember the algorithm used to convert from one base to another (in fact, the algorithm that we mostly use to convert from decimal to any other base)?, if not, well, suppose you want to convert the decimal number 18 to binary, you simply divide the number by the base until the quotient is less than or equal to the base, then you read the result from right to left, for example:

 

18 2 0 8 2 1 4 2 0 2 2 0 1		18 2 0 8 2 1 4 2 0 2 2 0 1 ←
		reading from right to left
		(18)10 = (10010)2

 

A sample code for this algorithm (in C++) is the following: There you have it, we have used this algorithm many times before (some people may have it skull engraved) but have you ever asked "how this algorithm works?", well this article will show you an interesting property of this algorithm that has a relation with the digit separation algorithm and hopefuly will show you how the thing work.

 

Testing the algorithm

 

Given a set of digits of $n$ digits $d_{i}$ that represent a number in base $b$ (where $b$ is usually between 2 and 36), the number can be converted to decimal using the following expression:

 

\begin{equation}\label{eq:nval} N=\sum_{i=0}^{n-1}d_{i}.b^{i} \end{equation}

 

Applying equation (\ref{eq:nval}) in the above example, we get: \[ \left(10010\right)_{2}=\sum_{i=0}^{5-1}d_{i}.2^{i}=1.2^{4}+0.2^{3}+0.2^{2}+1.2^{1}+0.2^{0}=\left(18\right)_{10} \] So, we use the succesive division algorithm to find all the $d_{i}$, and it works for the general case, but how?

 

Searching a function for $d_{i}$, getting individual digits from a number

 

Maybe you have done this task before, given a number $N$, getting the $i$th digit from it. This is especially easy in base 10, for example, given the number 54787, to obtain the diferent digits you divide by powers of 10 and take the modulo 10. Lets define the digits function $D(x, i)$ that takes the index $i$ of the digit you want from the number $x$ starting in 1: \[ \begin{array}{c} D(54787,1)=54787\mod10=7\\ D(54787,2)=\left\lfloor \frac{54787}{10}\right\rfloor \mod10=8\\ D(54787,3)=\left\lfloor \frac{54787}{10^{2}}\right\rfloor \mod10=7\\ D(54787,4)=\left\lfloor \frac{54787}{10^{3}}\right\rfloor \mod10=4\\ D(54787,5)=\left\lfloor \frac{54787}{10^{4}}\right\rfloor \mod10=5\\ \ldots\\ D(x,i)=\left\lfloor \frac{x}{10^{i-1}}\right\rfloor \mod10=d_{i} \end{array} \] Something about this equation, it works for any base $b$, so you can generalize it as: \begin{equation}\label{eq:ndigit} D(x,b,i)=\left\lfloor \frac{x}{b^{i-1}}\right\rfloor \mod b=d_{i} \end{equation}

 

Yes, it works for any base $b$, let's apply this with $\left(18\right)_{10} = \left(10010\right)_{2}$: \[ \begin{array}{c} D(\left(10010\right)_{2},2,1)=\left(18\right)_{10}\mod2=0\\ D(\left(10010\right)_{2},2,2)=\left\lfloor \frac{\left(18\right)_{10}}{\left(2\right)_{10}}\right\rfloor \mod2=1\\ D(\left(10010\right)_{2},2,3)=\left\lfloor \frac{\left(18\right)_{10}}{\left(2^{2}\right)_{10}}\right\rfloor \mod2=0\\ D(\left(10010\right)_{2},2,4)=\left\lfloor \frac{\left(18\right)_{10}}{\left(2^{3}\right)_{10}}\right\rfloor \mod2=0\\ D(\left(10010\right)_{2},2,5)=\left\lfloor \frac{\left(18\right)_{10}}{\left(2^{4}\right)_{10}}\right\rfloor \mod2=1 \end{array} \] Check out that the divisions were made using base 10, you can choose the base you feel more confortable to do the division (I prefer to divide by 10 that by 2), as both numbers remain in the same base there is no problem.

 

The succesive division algorithm is the function $D(x, b, i)$ in disguise!

 

That's right, check for yourself, the succesive division is a way to get all digits in one run using the function $D(x, i)$ with each iteration. You start dividing 18 by 2 and take the remainder of the division as the rightmost digit (the same as taking the mod 2 from the number): \[ D(18, 2, 1) = \left(18\right)_{10} \mod 2 = 0 \] The algorithm's next step is to take the quotient from the previous division and divide it again by 2, taking the remainder as the next digit from right to left (the same as dividing the original number by 2 and taking the mod 2 from the quotient) \[ D(18, 2, 2) = \left\lfloor \frac{18}{2}\right\rfloor \mod2=1\\ \] And so on... So the algorithm is a way to apply the general $D(x, b, i)$ function doing the calculations over $x$ in base 10.

 

Conclusion

 

Applying equation (\ref{eq:ndigit}) in equation (\ref{eq:nval}), we get: \[ v=\sum_{i=0}^{n-1}D(x,b,i+1).b^{i}=\sum_{i=0}^{n-1}(\left\lfloor \frac{x}{b^{i}}\right\rfloor \mod b).b^{i} \] We have replaced the $d_{i}$ with the digits formula and divised that the, sometimes imposed, algorithm that we have used since kids to convert to binary (or any other base) is just a way to use the $D$ function that saves some calculations.