# Converting Decimal to Other Bases Reverse Remainder Collection

The question is why is it that when we convert base 10 to other bases -- base 2, in particular -- we repeatedly divide the number by the new base while keeping track of the remainders and then collect the remainders in the REVERSE order.

It appears at first site that the remainders should be collected as they appear. That is,

17 / 2 = 8, r = 1

8 / 2 = 4, r = 0

4 / 2 = 2, r = 0

2 / 2 = 1, r = 0

The result is 1001. While it is correct, it seems a bit counterintuitive that the first remainder which is the result of dividing the largest number by the new base produces the least significant digit in the answer.

• You should have constructed an example where the number is not symmetric in base $2$ in the example, since you emphasized the "REVERSE." Something like $23$. – Thomas Andrews Jul 19 '17 at 18:38
• Why on earth does that seem counter intuitive? You are dividing the smallest power of the base first so you will get the finest smallest least significant remainder first. Seems utterly logical and intuitive to me. The remainder of dividing by $b^1$ will be a remainder between $0$ and $b$ where's dividing by $b^2$ will be a remainder of degree 2 between 0 and $b^2$. – fleablood Jul 19 '17 at 18:38
• @fleablood That is a good way of looking at it :) – MadPhysicist Jul 19 '17 at 18:41
• Another thing to note is that there is purely human notation to write $7\cdot 1 +1\cdot 10+5\cdot 10^2$ as $517$. We could just as well have chosen to right them in the reverse order as our notation (and mathematically, it is easier to work with them in the order 7,1,5, in some circumstances.) – Thomas Andrews Jul 19 '17 at 18:41
• Just imagine if you were asked to convert $137$ in base $10$ to base $10$. Divide $137$ by $10$ and you get $13$ with a remainder of $7$. – Thomas Andrews Jul 19 '17 at 18:42

## 1 Answer

This is just a by-product of Horner's scheme for evaluation of polynomials. I'll explain from your example.

The algorithm may be described as follows:

Set $q_0$ be your number ($17$), and $r_0=q_0\bmod 2$. We recursively compute $q_i$, $r_i$ with the Euclidean division : $$q_i=q_{i+1}\cdot 2+r_i, \quad r_i=0\;\text{ or }\;1,$$ and stop when a quotient is equal to $1$.

In the present case ($4$ steps), we obtain successively: \begin{align} 17&=q_1\cdot 2+ r_0=(q_2\cdot 2+ r_1)2+r_0\\ &=q_2\cdot 2^2+r_1\cdot 2+r_0=(q_3\cdot 2+ r_2)2^2+r_1\cdot 2+r_0 \\ &=q_3\cdot 2^3 +r_2\cdot 2^2+r_1\cdot 2+r_0=(q_4\cdot 2+r_4) 2^3 +r_2\cdot 2^2+r_1\cdot 2+r_0 \\ &=q_4\cdot2^4+r_3\cdot2^3 +r_2\cdot 2^2+r_1\cdot 2+r_0 . \end{align}

Hence $17$ (base $10$) is $\;[q_4r_3r_2r_1r_0]_2=_2$.