Skip to main content

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.

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.

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\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.6.3.

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

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 =\)

Answer 1.

\(4\)

Answer 2.

\(6\)

Answer 3.

\(1\)

Answer 4.

\(4\)

Answer 5.

\(2\)

Answer 6.

\(16\)

Answer 7.

\(3\)

Answer 8.

\(64\)

Answer 9.

\(4\)

Answer 10.

\(256\)

Answer 11.

\(5\)

Answer 12.

\(1024\)

Answer 13.

\(6\)

Answer 14.

\(4096\)

Answer 15.

\(4096\)