PA2: Loop Invariants

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

Program Submission

Submit your assignment using the checkin system. Submit your source code as a single file named eExp.py.