Algorithm 11.21. Base Conversion.
- Input:
- Output:
- The base \(b\) digits \(r_0,\dots,r_m\in\Z_b\) of \(a\) such that \(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\)
-
repeat
Section 11.5 From 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.22 we go through the steps of Algorithm 11.21 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.21 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.26 click through the steps of the algorithm for various input values/
Example 11.23. From decimal to base \(3\) with Algorithm 11.21.
We convert the base 10 number 23 to base 3 using Algorithm 11.21.
| \(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\) |
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{.}\)
Example 11.24. From decimal to base 11 with Algorithm 11.21.
We convert \(2619\) from decimal representation to base \(11\) representation. As the input to Algorithm 11.21 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{.}\)
Example 11.25. From decimal to base 16 with Algorithm 11.21.
| \(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\) |
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.26.
