## Section2.6Exponentiation 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$$ , 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$$ . 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 .

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 =$$

$$4$$

$$6$$

$$1$$

$$4$$

$$2$$

$$16$$

$$3$$

$$64$$

$$4$$

$$256$$

$$5$$

$$1024$$

$$6$$
$$4096$$
$$4096$$