## Section11.5From Decimal to Base $$b$$

Let $$a\in\N\text{.}$$ Finding the base $$b$$ expansion of $$a$$ means finding integers $$r_0\text{,}$$ $$r_1\text{,}$$ $$r_2\text{,}$$ $$\ldots\text{,}$$ $$r_{m-1}\text{,}$$ and $$r_m$$ from $$0$$ to $$b-1$$ such that

\begin{equation*} a=r_m\cdot b^m+r_{m-1}b^{m-1}+\dots+r_3\cdot b^3+r_2\cdot b^2+r_1\cdot b+r_0. \end{equation*}

We proceed from right to left to find $$r_0\text{,}$$ $$r_1\text{,}$$ $$r_2\text{,}$$ $$\ldots\text{,}$$ $$r_{m-1}\text{,}$$ and $$r_m\text{.}$$

Let $$r_0=a\fmod b$$ be the remainder of the division of $$a$$ by $$b\text{.}$$ Then

\begin{equation*} a=q_0\cdot b+r_0\text{.} \end{equation*}

As $$q_0\cdot b$$ is divisible by $$b$$ we have that $$r_0$$ the rightmost base $$b$$ digit of $$a\text{.}$$

We now continue this procedure with $$q_0=a\fdiv b\text{.}$$ Let $$r_1=q_0\fmod b$$ be the remainder of the division of $$q_0$$ by $$b$$ and $$q_1=q_0\fdiv b\text{.}$$ Then $$q_0=q_1\cdot b+r_1\text{.}$$ Replacing $$q_0$$ in $$a=q_0\cdot b+r_0$$ by $$q_0=q_1\cdot b+r_1$$ we get

\begin{equation*} a=q_0\cdot b+r_0=(q_1\cdot b+r_1)b+r_0=q_1\cdot b^2+r_1\cdot b+r_0\text{.} \end{equation*}

Continuing in this way, we successively compute the digits $$r_2\text{,}$$ $$r_3$$ and so on of the base $$b$$ expansion of $$a$$ using divisions with remainders. The quotient becomes smaller in every step. As the quotient is a non-negative integer, it eventually has to become $$0\text{.}$$ Then we stop.

We formulate this process as an algorithm. Instead of introducing a new variable $$q_i$$ in every iteration we reuse the variable $$a\text{.}$$

In the video in Figure 11.5.2 we go through the steps of Algorithm 11.5.1 and convert a number from base $$10$$ representation to base $$12$$ representation.

In our examples we write down the computations in the repeat_until loop in Algorithm 11.5.1 in the row of a table. We start with a base $$3$$ example, continue with base $$11$$ and base $$16$$ and a base $$23$$ examples. In Example 11.5.6 click through the steps of the algorithm for various input values/

We convert the base 10 number 23 to base 3 using Algorithm 11.5.1.

Input: $$b=3\text{,}$$ $$a=23$$

 $$i=0$$ $$r_0=23 \fmod 3=2$$ $$a=23\fdiv 3 =7$$ $$i=1$$ $$r_1=7 \fmod 3=1$$ $$a=7\fdiv 3 =2$$ $$i=2$$ $$r_2=2 \fmod 3=2$$ $$a=2\fdiv 3 =0$$

Output: $$r_0 = 2\text{,}$$ $$r_1 = 1\text{,}$$ $$r_2 = 2$$

The base 3 expansion of 23 is $$23=2 \cdot 3^2+1 \cdot 3+ 2 \cdot 1\text{.}$$ Thus the base $$3$$ representation of $$23$$ is $$212_3\text{.}$$

We convert $$2619$$ from decimal representation to base $$11$$ representation. As the input to Algorithm 11.5.1 we have $$b=11$$ and $$a=2619\text{.}$$

 $$i=0$$ $$r_0=2619 \fmod 11=1$$ $$a=2619\fdiv 11 =238$$ $$i=1$$ $$r_1=238 \fmod 11=7$$ $$a=238\fdiv 11 =21$$ $$i=2$$ $$r_2=21 \fmod 11=10$$ $$a=21\fdiv 11 =1$$ $$i=3$$ $$r_3=1 \fmod 11=1$$ $$a=1\fdiv 11 =0$$

The base $$11$$ expansion of $$2619$$ is $$2619=1 \cdot 11^3+10\cdot11^2+7\cdot 11+1\cdot 1\text{.}$$

Since $$10=\mathrm{A}_{11}\text{,}$$ the base $$11$$ representation of $$2619$$ is $$1\mathrm{A}71_{11}\text{.}$$

We convert the base $$10$$ number $$1709$$ to base $$16$$ using Algorithm 11.5.1.

Input: $$b=16\text{,}$$ $$a=1709$$

 $$i=0$$ $$r_0=1709 \fmod 16=13$$ $$a=1709\fdiv 16 =106$$ $$i=1$$ $$r_1=106 \fmod 16=10$$ $$a=106\fdiv 16 =6$$ $$i=2$$ $$r_2=6 \fmod 16=6$$ $$a=6\fdiv 16 =0$$

Output: $$r_0 = 13\text{,}$$ $$r_1 = 10\text{,}$$ $$r_2 = 6$$

The base 16 expansion of 1709 is $$1709= 6 \cdot 16^2 + 10 \cdot 16 + 13 \cdot 1\text{.}$$ Since $$10=\mathrm{A}_{16}$$ and $$13=\mathrm{D}_{16}\text{,}$$ the base 16 representation of $$1709$$ is $$6\mathrm{A}\mathrm{D}_{16}\text{.}$$

Investigate further examples by clicking your way through the steps of the interactive base conversion algorithm in Example 11.5.6.

In Checkpoint 11.5.7 apply Algorithm 11.5.1 to convert a number in base $$10$$ representation to a different base representation.

With the conversion algorithm find the base $$15$$ representation of the decimal number $$43537\text{.}$$

Input: Base $$b :=$$ and a base 10 number $$a :=$$

Let $$q_0:=a\text{.}$$

Let $$r_{0} := q_{0}\bmod b =$$ . Let $$q_{1} := a_{0}\;\mathrm{div}\; b =$$ .

Let $$r_{1} := q_{1}\bmod b =$$ . Let $$q_{2} := a_{1}\;\mathrm{div}\; b =$$ .

Let $$r_{2} := q_{2}\bmod b =$$ . Let $$q_{3} := a_{2}\;\mathrm{div}\; b =$$ .

Let $$r_{3} := q_{3}\bmod b =$$ . Let $$q_{4} := a_{3}\;\mathrm{div}\; b =$$ .

Output: The expanded base $$15$$ representation of the decimal number $$43537$$ is:

$$43537=r_{3}\cdot 15^{3}$$

$$+r_{2}\cdot 15^{2}$$

$$+r_{1}\cdot 15^{1}$$

$$+r_{0}\cdot 15^{0}$$

$$\phantom{43537}=$$$$\cdot 15^{3}$$

$$+$$$$\cdot 15^{2}$$

$$+$$$$\cdot 15^{1}$$

$$+$$$$\cdot 15^{0}$$

Now give the base $$15$$ representation of $$43537\text{.}$$

[Although writing leading zeros is mathematically correct, it will be marked as wrong. Do not put extra zeros in front of your answer. For example, you would write 101 instead of 0101.

Be careful to write $$A$$ for $$10$$ and $$B$$ for $$11$$ and $$C$$ for $$12$$ and so on.

]

$$43537 =$$$${}_{15}$$

$$15$$

$$43537$$

$$7$$

$$2902$$

$$7$$

$$193$$

$$13$$

$$12$$

$$12$$

$$0$$

$$12$$

$$13$$

$$7$$
$$7$$