Skip to main content \(\newcommand{\longdivision}[2]{#1\big)\!\!\overline{\;#2}}
\newcommand{\mlongdivision}[2]{\longdivision{#1}{#2}}
\renewcommand{\emptyset}{\{\}}
\newcommand{\blanksp}{\underline{\hspace{.25in}}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\cspace}{-}
\newcommand{\Ta}{\mathtt{a}}
\newcommand{\Tb}{\mathtt{b}}
\newcommand{\Tc}{\mathtt{c}}
\newcommand{\Td}{\mathtt{d}}
\newcommand{\Te}{\mathtt{e}}
\newcommand{\Tf}{\mathtt{f}}
\newcommand{\Tg}{\mathtt{g}}
\newcommand{\Th}{\mathtt{h}}
\newcommand{\Ti}{\mathtt{i}}
\newcommand{\Tj}{\mathtt{j}}
\newcommand{\Tk}{\mathtt{k}}
\newcommand{\Tl}{\mathtt{l}}
\newcommand{\Tm}{\mathtt{m}}
\newcommand{\Tn}{\mathtt{n}}
\newcommand{\To}{\mathtt{o}}
\newcommand{\Tp}{\mathtt{p}}
\newcommand{\Tq}{\mathtt{q}}
\newcommand{\Tr}{\mathtt{r}}
\newcommand{\Ts}{\mathtt{s}}
\newcommand{\Tt}{\mathtt{t}}
\newcommand{\Tu}{\mathtt{u}}
\newcommand{\Tv}{\mathtt{v}}
\newcommand{\Tw}{\mathtt{w}}
\newcommand{\Tx}{\mathtt{x}}
\newcommand{\Ty}{\mathtt{y}}
\newcommand{\Tz}{\mathtt{z}}
\newcommand{\So}{\Tf}
\newcommand{\Sno}{\Tg}
\newcommand{\Si}{\Th}
\newcommand{\Sni}{\Tj}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\ZZ}{\Z}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\RR}{\R}
\newcommand{\F}{\mathbb{F}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\abs}[1]{|#1|}
\newcommand{\fmod}{\bmod}
\newcommand{\fdiv}{\,\mathrm{div}\,}
\newcommand{\lcm}{\mathrm{lcm}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\nr}[1]{\##1}
\newcommand{\gexp}[3]{#1^{#2 #3}}
\newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}}
\newcommand{\glog}[3]{\log_{#1}^{#3}#2}
\newcommand{\sol}[1]{{\color{blue}\textit{#1}}}
\newcommand{\gro}[1]{{\color{gray}#1}}
\newcommand{\todo}[1]{{\color{purple}TO DO: #1}}
\newcommand{\fixme}[1]{{\color{red}FIX ME: #1}}
\newcommand{\checkme}[1]{{\color{green}CHECK ME: #1}}
\newcommand{\degre}{^\circ}
\newcommand{\vect}[1]{\overrightarrow{#1}}
\newcommand{\nix}{}
\newcommand{\cox}[1]{\fcolorbox[HTML]{000000}{#1}{\phantom{M}}}
\newcommand{\tox}[1]{\texttt{\##1} \amp \cox{#1}}
\newcommand{\ttx}[1]{\texttt{\##1}}
\newcommand{\mox}[1]{\mathtt{\##1}}
\newcommand{\xx}{\mathtt{\#}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
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{.}\)
Algorithm 11.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\)
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.
Figure 11.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/
Example 11.29 . From decimal to base \(3\) with Algorithm 11.27.
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{.}\)
Example 11.30 . From decimal to base 11 with Algorithm 11.27.
We convert
\(2619\) from decimal representation to base
\(11\) representation. As the input to
Algorithm 11.27 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.31 . From decimal to base 16 with Algorithm 11.27.
We convert the base
\(10\) number
\(1709\) to base
\(16\) using
Algorithm 11.27 .
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.32 .
Example 11.32 . Conversion to base b representation interactive.
Checkpoint 11.33 . Covert from decimal to other base.
