Question

As an example exercise, we were asked to find the loop invariant for this bit of code.

def mystery(a,b):
    # Precondition: a >= 0 and b >= 0
    while a >= 0 and b >= 0:
        if a < b:
            a, b = b, a
        else:
            a = a - 1
    return a

From what I can see, it first ensures that a >= b.
After that, each loop iteration decreases the value of a by 1.

This will continue until a and b are 0.

Then one final iteration terminates the loop with a == -1.

However from what I can tell, if the loop invariant is something like a >= b, it fails upon termination as a = -1 and b = 0.

Could anyone tell me the actual loop invariant of this function as I'm a bit confused.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top