# MAT 112 Integers and Modern Applications for the Uninitiated

## 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.22.
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.

### Example2.45.Computing $$5^3$$ with Algorithm 2.44.

We compute $$5^3$$ with Algorithm 2.44.
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.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.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.46.

### Example2.46.Exponentiation algorithm interactive.

In the Checkpoint 2.47 we unroll the loop in Algorithm 2.44. Follow the instructions to compute the power.

### Checkpoint2.47.Use Algorithm 2.44.

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