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
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
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{.}\)
Algorithm11.27.Base Conversion.
Input:
A base \(b\in\N\) with \(b\ne 1\) and \(a\in\N\)
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\)
let\(i:=0\)
repeat
let\(r_i := a\fmod b\)
let\(a := a\fdiv b\)
let\(i := i+1\)
until\(a=0\)
return\(r_0,\dots,r_m\)
In the video in Figure 11.28 we go through the steps of Algorithm 11.27 and convert a number from base \(10\) representation to base \(12\) representation.
Figure11.28.Conversion form Base 10 to Base b (by Matt Farmer and Stephen Steward)
In our examples we write down the computations in the repeat_until loop in Algorithm 11.27 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.32 click through the steps of the algorithm for various input values/
Example11.29.From decimal to base \(3\) with Algorithm 11.27.
We convert the base 10 number 23 to base 3 using Algorithm 11.27.
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.32.
Example11.32.Conversion to base b representation interactive.
In Checkpoint 11.33 apply Algorithm 11.27 to convert a number in base \(10\) representation to a different base representation.
Checkpoint11.33.Covert from decimal to other base.
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.
