3925.sagews

$\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)