'''
20211005

Robin Dawes

Compares iterative and recursive approaches for computing x**y, where
y is a non-negative integer.

The second recursive method is far superior to the other methods in
terms of the reduced amount of work it executes to get the answer.
'''

total_multiplications = 0                    # This is used as a global variable in the
                                                           # functions to count the number of 
                                                           # multiplications needed to find the 
                                                           # desired power of x

def exponent_iterative(x, y):
   '''returns x**y
      requires that y is a non-negative integer
   '''
   global total_multiplications
   value = 1
   for i in range(y):
      value *= x
      total_multiplications += 1
   return value
   
   
   
def exponent_recursive(x, y):
   '''returns x**y
      requires that y is a non-negative integer
   '''
   global total_multiplications
   if y == 0:
      return 1
   else:
      total_multiplications += 1
      return x * exponent_recursive(x, y-1)
      
      
      
def smart_exponent_recursive(x, y):
   '''returns x**y
      requires that y is a non-negative integer
      
      The algorithm in use here is based on computing 
      x**y = (x**(y//2))**2 when y is even, and
      x**y = (x**(y//2))**2 * x when y is odd
   '''
   global total_multiplications
   if y == 0:
      return 1
   else:
      reduced_y = y // 2
      temp = smart_exponent_recursive(x, reduced_y)
      if y % 2 == 0:
         total_multiplications += 1
         return temp*temp
      else:
         total_multiplications += 2
         return temp*temp*x
         

total_multiplications = 0         
print(exponent_iterative(3,23))
print("That used", total_multiplications, "multiplications\n")

total_multiplications = 0
print(exponent_recursive(3,23))
print("That used", total_multiplications, "multiplications\n")

total_multiplications = 0
print(smart_exponent_recursive(3,23))
print("That used", total_multiplications, "multiplications\n")