Converting Decimal to Other Bases Reverse Remainder Collection

754 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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=[10001]_2$.