Exponentiation Algorithm

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}{\mbox{--}} \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 2.6 Exponentiation Algorithm

We present an algorithm for computing a power of an integer. We call this algorithm the Naive Exponentiation algorithm, since there is a more clever way of calculating powers which we will present with Algorithm 15.3.5 .

Algorithm 2.6.1. Naive Exponentiation for Integers.

Input:: An integer \(b\) and a non-negative integer \(n\)
Output:: \(\displaystyle b^n\)

if \(n=0\) then return \(1\)
let \(c:=1\)
let \(i:=0\)
repeat
1. let \(c:=c\cdot b\)
2. let \(i:= i+1\)
until \(i=n\)
return \(c\)

In this algorithm, the number of steps in the sequence of computations, \(n\) , is directly given as one of the inputs. We demonstrate this algorithm with a numerical example.

Example 2.6.2. Computing \(5^3\) with Algorithm 2.6.1.

We compute \(5^3\) with Algorithm 2.6.1 .

Input: \(b=5\) and \(n=3\)

1. As \(3\ne 0\) we continue with step 2

2. let \(c:=1\)

3. let \(i:=0\)

4.a. let \(c:=1\cdot 5=5\)

4.b. let \(i:=0+1=1\)

5. As \(i=1\) and \(n=3\) the statement \(i=n\) is false. We continue with step 4 4.a..

4.a. let \(c:=5\cdot 5=25\)

4.b. let \(i:=1+1=2\)

5. As \(i=2\) and \(n=3\) the statement \(i=n\) is false. We continue with step 4 4.a..

4.a. let \(c:=5\cdot 25=125\)

4.b. let \(i:=2+1=3\)

5. As \(i=3\) and \(n=3\) we have \(i=n\) . We continue with step 6 .

6. We return the value of \(c\) which is 125.

Output: \(125\)

We have computed \(5^3=125\) .

Work through further the exponentiation algorithm with other input values in Example 2.6.3 .

Example 2.6.3. Exponentiation algorithm interactive.

In the Checkpoint 2.6.4 we unroll the loop in Algorithm 2.6.1 . Follow the instructions to compute the power.

Checkpoint 2.6.4. Use Algorithm 2.6.1.

Exponentiation

Input: Base \(b :=\) an exponent \(n:=\) .

\(\quad\) let i:=0 and let \(c:=1\text{.}\)

\(\quad\) let i:=i+1= and let \(c:=c\cdot 4=\) .

\(\quad\) let i:=i+1= and let \(c:=c\cdot 4=\) .

\(\quad\) let i:=i+1= and let \(c:=c\cdot 4=\) .

\(\quad\) let i:=i+1= and let \(c:=c\cdot 4=\) .

\(\quad\) let i:=i+1= and let \(c:=c\cdot 4=\) .

\(\quad\) let i:=i+1= and let \(c:=c\cdot 4=\) .

Because the statement \(i=6\) is true, we end the loop.

Output: \(c =\)

\(4\)

\(6\)

\(1\)

\(4\)

\(2\)

\(16\)

\(3\)

\(64\)

\(4\)

\(256\)

\(5\)

\(1024\)

\(6\)

\(4096\)

\(4096\)