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.22.
Algorithm 2.44. 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
let \(c:=c\cdot b\)
let \(i:= i+1\)
until \(i=n\)
return \(c\)
In this algorithm, the number of steps in the sequence of computations, \(n\text{,}\) is directly given as one of the inputs. We demonstrate this algorithm with a numerical example.
Example 2.45. Computing \(5^3\) with Algorithm 2.44.
Input: \(b=5\) and \(n=3\)
1. As
\(3\ne 0\) we continue with
step 2.
4.a.
let \(c:=1\cdot 5=5\)
5. As
\(i=1\) and
\(n=3\) the statement
\(i=n\) is false. We continue with
step 4.a.
4.a.
let \(c:=5\cdot 5=25\)
5. As
\(i=2\) and
\(n=3\) the statement
\(i=n\) is false. We continue with
step 4.a.
4.a.
let \(c:=5\cdot 25=125\)
5. As
\(i=3\) and
\(n=3\) we have
\(i=n\text{.}\) We continue with
step 6.
6. We return the value of
\(c\) which is 125.
Output: \(125\)
We have computed \(5^3=125\text{.}\)
Work through further the exponentiation algorithm with other input values in
Example 2.46.
Example 2.46. Exponentiation algorithm interactive.
Checkpoint 2.47. Use Algorithm 2.44.
