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)