This second python programming assignment, PA2, is about loop invariants. You will write a function eExp(left,right) that computes exponentials left ** right in a similar fashion as the egyptian_multiplication function computes products, as discussed in lecture 8: loop invariants.

eExp.txt contains some skeleton code. Download it and rename it eExp.py. Study egyptian multiplication in the lecture. The program logic in egyptian_multiplication, and thus the loop invariant is based on the fact that

 a * b = if odd(a): b + (a//2)*(b*2) else: (a//2)*(b*2) 

and that p stepwise gathers the product.

For your exponentiation code, the program logic, and thus the loop invariant, is based on the fact that

 n ** k = if odd(k): n * (n*n)**(k//2) else (n*n)**(k//2) 

and that e stepwise gathers the exponential.

Your job is to complete the code **INCLUDING** the correct assert statements to check the loop invariant, loop test and their combination, as indicated in the skeleton code. Leave the print statements in place. A correct implementation of eExp:

 python3 eExp.py 2 11 

produces

 program: eExp.py 2 11 n: 2 k: 11 e: 1 n: 4 k: 5 e: 2 n: 16 k: 2 e: 8 n: 256 k: 1 e: 8 k: 0 e: 2048 2 ** 11 = 2048 

exp.txt

mport sys def eExp(left, right): # precondition: left>0 AND right>0 if left <= 0 or right <= 0 : raise "eExp: invalid inputs!" n=left; k=right; e=1 #e: the exponent assert True # fill in the proper loop invariant while (False) : # the loop test assert True # fill in the proper loop test and loop invariant print(" n:",n,"k:",k,"e:",e) # body assert True # fill in the proper loop invariant print("k:",k,"e:",e) assert True # fill in proper not(loop test) and loop invariant return e if __name__ == "__main__": print("program:", sys.argv[0], sys.argv[1], sys.argv[2]) n = int(sys.argv[1]) k = int(sys.argv[2]) e = eExp(n,k) print(n,"**",k,"=",e)