CS 520: Exponents
Mark Boady
Department of Computer Science
Drexel University
April 26, 2020
Mark Boady CS 520: Exponents 1 / 20
Three Methods to Compute an Exponent
Method 1: Using only Additions
Method 2: Using multiplications
Method 3: Fast Powering
Mark Boady CS 520: Exponents 2 / 20
Method 1
Implement exponent using only addition.
1: function powerM1(a,b)
| 2: 3: 4: 5: 6: 7: 8: 9: 10: |
Let total = 1 for x=0; i < b; x++ do subtotal = 0 for y=0; y < a; y++ do subtotal = subtotal + total end for total = subtotal end for return total |
11: end function
Mark Boady CS 520: Exponents 3 / 20
Method 1 Example
What happens if we compute 24? (a=2, b=4)
| Iteration | x < b | y < a | total | subtotal |
| Initial | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 2 |
| 2 | 1 | 0 | 2 | 2 |
| 3 | 1 | 1 | 2 | 4 |
| 4 | 2 | 0 | 4 | 4 |
| 5 | 2 | 1 | 4 | 8 |
| 6 | 3 | 0 | 8 | 8 |
| 7 | 3 | 1 | 8 | 16 |
| Return | 16 | 16 |
Mark Boady CS 520: Exponents 4 / 20
Coming up with a Formula
Start with the inner most loop
for y=0; y < a; y++ do
subtotal = subtotal + total
end for
Assume the addition/assignment is a constant amount of work
We do it repeatedly for every value from 0 up to a
Since we have y < a, it doesn’t execute when y = a.
This gives us a summation:
a-1
Xy
=0
1
Mark Boady CS 520: Exponents 5 / 20
Determining the outer loop
Next, we examine the outer loop.
1: for x=0; i < b; x++ do
2: [Some Stuff Happens]
3: end for
This loop repeats for values from x to b – 1.
b-1
Xx
=0
(Inner Loop Runs)
We can put both the pieces together to get
T(a; b) =
b-1
Xx
=0
a-1
Xy
=0
1
Mark Boady CS 520: Exponents 6 / 20
Method 1’s Runtime
Solve the summation
T(a; b) =
b-1
Xx
=0
a-1
Xy
=0
1 (1)
=
b-1
Xx
=0
a Inner Sum runs a times. (2)
=a
b-1
Xx
=0
1 Factor out (3)
=ab Sum runs b times. (4)
T(a; b) =Θ (ab) (5)
T(a; b) =O max(a; b)2 (6)
The larger of a2 and b2 is an upper bound.
Mark Boady CS 520: Exponents 7 / 20
Method 2
Implement exponent as repeated multiplications.
1: function powerM2(a,b)
| 2: 3: 4: 5: 6: |
total =1 for x=0; x<b;x++ do total = total * a end for return total |
7: end function
Mark Boady CS 520: Exponents 8 / 20
Method 2 Example
What happens if we computer 24? (a=2, b=4)
| Iteration | x < b | total |
| Initial | 0 | 1 |
| 0 | 0 | 2 |
| 1 | 1 | 4 |
| 2 | 2 | 8 |
| 3 | 3 | 16 |
| Return | 16 |
Mark Boady CS 520: Exponents 9 / 20
Method 2 Analysis
A multiplication takes constant time 1.
The number of multiplications is determined by b.
This is a linear solution instead of a quadratic solution.
T (b) =
b-1
Xx
=0
1 (7)
=b (8)
T (b) =Θ(b) (9)
T (b) =O(b) (10)
Mark Boady CS 520: Exponents 10 / 20
Method 3
Compute Exponent using repeated squaring
Recursive functions require recursive time functions
We will solve for a closed form
function powerM3(a,b)
if b==0 then
return 1
else if b==1 then
return a
else if b%2==0 then
return powerM3(a*a,b/2)
else
return a*powerM3(a,b-1)
end if
end function
Mark Boady CS 520: Exponents 11 / 20
Method 2 Example
What happens if we computer 24? (a=2, b=4)
| Function Call | b | Return Value |
| powerM3(2,4) | 4%2 = 0 | powerM2(2*2=4,2) |
| powerM3(4,2) | 2%2 = 0 | powerM2(4*4=16,1) |
| powerM3(16,1) | b = 1 | 16 |
Mark Boady CS 520: Exponents 12 / 20
Method 2 Example
What happens if we computer 57? (a=5, b=7)
| Function Call | b | Return Value |
| powerM3(5,7) | 7%2 = 1 | 5*powerM2(5,6)=78125 |
| powerM3(5,6) | 6%2 = 0 | power(25,3) |
| powerM3(25,3) | 3%2 = 1 | 25*power(5,2)=15625 |
| powerM3(25,2) | 2%2 = 0 | power(625,1) |
| powerM3(625,1) | 1 = 1 | 625 |
Mark Boady CS 520: Exponents 13 / 20
Method 3 Formula
This function needs to be expression recursively.
To compute T(b) we need to know T(b=2).
A multiplication costs 1.
We will assume b is even.
T(b) = (1T(b=2) + 1 otherwise b = 1 (11)
Mark Boady CS 520: Exponents 14 / 20
Solve Recurrence
The zero case is also constant.
Odd cases do one action, then call an even case.
An odd numbers at most double the work. (Same Theta)
We can focus on even values b = 2n to get a bound
Expand the recurrence to find a pattern
| T(b) =T(b=2) + 1 T(b) = [T(b=4)) + 1] + 1 T(b) = [T(b=8) + 1] + 1 + 1 T(b) = [T(b=16) + 1] + 1 + 1 + 1 |
(12) (13) (14) (15) |
Mark Boady CS 520: Exponents 15 / 20
Solve Recurrence
Look for a Pattern
| T(b) =T(b=2) + 1 T(b) =T(b=4) + 2 T(b) =T(b=8) + 3 T(b) =T(b=16) + 4 T(b) =T(b=2k) + k |
(16) (17) (18) (19) (20) |
Mark Boady CS 520: Exponents 16 / 20
Solve Recurrence
T(b) = T(b=2k) + k
Find out when it hits the base case (solve for k)
When do we get T(1)?
The recursive call is T(b=2k).
When does b=2k = 1?
| 1 =b=2k 2k =b k = log2(b) |
(21) (22) (23) |
Mark Boady CS 520: Exponents 17 / 20
Solve Recurrence
Plug into expression
T(b) = T(b=2k) + k
k = log2(b)
| T(b) =T(b=2k) + k =T(b=2log2(b)) + log2(b) =T(b=b) + log2(b) =T(1) + log2(b) =1 + log2(b) =Θ (log2(b)) |
(24) (25) (26) (27) (28) (29) |
Mark Boady CS 520: Exponents 18 / 20
Method Comparison
Compare three methods to compute exponent
Method 1: Θ (a ∗ b)
Method 2: Θ (b)
Method 3: Θ (log2(b))
Method 3 is best!
Mark Boady CS 520: Exponents 19 / 20
Analyzing Algorithms
We can also see this experimentally
Seconds to compute values shown.
| Exponent | Method 1 | Method 2 | Method 3 |
| 1132 | 1.02043e-04 | 6.91414e-06 | 5.96046e-06 |
| 1164 | 1.38044e-04 | 8.82149e-06 | 5.00679e-06 |
| 11128 | 1.99080e-04 | 2.78950e-05 | 5.00679e-06 |
| 11256 | 3.88145e-04 | 3.69549e-05 | 5.00679e-06 |
| 11512 | 8.67128e-04 | 8.29697e-05 | 9.05991e-06 |
| 111024 | 2.11000e-03 | 1.80960e-04 | 1.71661e-05 |
| 112048 | 6.87289e-03 | 1.15705e-03 | 1.24931e-04 |
| 114096 | 2.02532e-02 | 2.02084e-03 | 1.63078e-04 |
| 118192 | 7.17490e-02 | 6.11806e-03 | 4.12941e-04 |
| 1116384 | 2.18037e-01 | 3.32670e-02 | 1.66893e-03 |
| 1132768 | 8.39085e-01 | 9.13410e-02 | 5.08213e-03 |
Mark Boady CS 520: Exponents 20 / 20
The post CS 520: Exponents Mark Boady appeared first on My Assignment Online.