Skip to main content
Logo image

Integers and Modern Applications for the Uninitiated

Sebastian Pauli

🔗

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.
🔗
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.45. Computing 53 with Algorithm 2.44.

🔗
We compute 53 with Algorithm 2.44.
🔗
Input: b=5 and n=3
🔗
  1. As 3≠0 we continue with step 2.
🔗
  2. let c:=1
🔗
  3. let i:=0
🔗
  4.a. let c:=1⋅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⋅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⋅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 53=125.
🔗
Work through further the exponentiation algorithm with other input values in Example 2.46.
🔗

Example 2.46. Exponentiation algorithm interactive.

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

Checkpoint 2.47. Use Algorithm 2.44.

Exponentiation
Input: Base b:= an exponent n:= .
let i:=0 and let c:=1.
let i:=i+1= and let c:=c⋅4= .
let i:=i+1= and let c:=c⋅4= .
let i:=i+1= and let c:=c⋅4= .
let i:=i+1= and let c:=c⋅4= .
let i:=i+1= and let c:=c⋅4= .
let i:=i+1= and let c:=c⋅4= .
Because the statement i=6 is true, we end the loop.
Output: c=
PrevTopNext