This second python programming assignment, PA2, is about loop invariants. You will write a function eExp(left,right) that comput
es 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)
