\mathbf{Problem}: Computing a^n for positive integer exponents.
(See pages 157-159 from Chapter 5 of the textbook titled "Introduction to The Design and Analysis of Algorithms", 2nd Edition by A. Levitin) \\
Here \mathbf{expa} function is an implementation for the \mathbf{decrease-(by-one)-and-conquer} algorithm (top down -recursive-).
\mathbf{expb} function is an implementation for the \mathbf{decrease-(by-one)-and-conquer} algorithm (bottom up same as the
brute force algorithm).
\mathbf{expc} function is an implementation for the \mathbf{decrease-(by-half)-and-conquer} algorithm (top down -recursive- algorithm).
import sys
sys.setrecursionlimit(15000)
def expa(a,n):
if n>1:
return expa(a,n-1)*a
else:
return a
def expb(a,n):
product=a
for g in range(0,n-1):
product=a*product
return product
def expc(a,n):
if (n%2)==0:
return expc(a,n/2)^2
elif (n%2)==1 and n>1:
return (expc(a,(n-1)/2)^2)*a
elif n==1:
return a
|
expa(2,40)
|
|
|
|