The algorithm of Euclid computes the greatest common divisor (GCD) of two integer numbers a and b. The following pseudo-code is the original version of this algorithm. Algorithm 1 Euclid1(a,b) Require: a, b > 0 Ensure: a = GCD(a, b) while a ̸= b do if a > b then a ← a − b else b ← b − a end if end while return a We want to prove the correctness of this algorithm using the loop invariant technique. a. In a first attempt to prove the correctness of this algorithm, we propose the following loop invariant property: “GCD(a, b) is a factor of a and b”. Explain why this property will not help you as is. b. Use your previous observation to propose another loop invariant property that will help you to prove the correctness of the version of Euclid’s algorithm presented above. c. Show that your loop invariant property is true before executing the While loop for the first time (i.e., initialization property)
The
Algorithm 1 Euclid1(a,b)
Require: a, b > 0
Ensure: a = GCD(a, b)
while a ̸= b do
if a > b then
a ← a − b
else
b ← b − a
end if
end while
return a
We want to prove the correctness of this algorithm using the loop invariant technique.
a. In a first attempt to prove the correctness of this algorithm, we propose the following loop invariant property: “GCD(a, b) is a factor of a and b”. Explain why this property will
not help you as is.
b. Use your previous observation to propose another loop invariant property that will
help you to prove the correctness of the version of Euclid’s algorithm presented above.
c. Show that your loop invariant property is true before executing the While loop for
the first time (i.e., initialization property)
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
