0
$\begingroup$

I'm reading this article on a GCD algorithm described by Dijkstra: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD316.4.html

I'm looking at program 1. In particular I'm trying to understand the proof that the loop terminates. Here is program 1 (my notation is slightly different than the one in the article):

function GCD(a,b) 

while a != b
    if a > b 
        a = a - b
    else
        b = b - a

return a

I get that max(a,b) at loop n is strictly greater than max(a,b) at loop n+1. Since a and b are integers greater than 0 it follows that max(a,b) is always greater than 0. This implies a lower bound. Therefore the while loop must terminate.

Is my understanding correct?

$\endgroup$
  • $\begingroup$ if a=1 and b=-1 the algorithm wil not terminate. If a,b are positive integers then the max(a,b) will strictly decrease. $\endgroup$ – miracle173 May 19 '18 at 10:02
  • $\begingroup$ The algorithm doesn't terminate if a ≤ 0 or b ≤ 0 unless initially a = b. $\endgroup$ – gnasher729 May 19 '18 at 10:39
1
$\begingroup$

If you just care about termination of the algorithm not the tight analysis then you can say that it will terminates within $a+b$ steps as inside the while loop you are decreasing either $a$ or $b$ depending on some condition, so your while loop have to terminate within $a+b$ iterations.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Note that you're always decreasing the larger of a and b, so you can give a tighter bound than this. $\endgroup$ – Draconis Jun 18 '18 at 15:23
1
$\begingroup$

Assuming that you start with positive integers, your reasoning is correct. max(a,b) strictly decreases and the loop will terminate before this value reaches zero (since the only way for it to become zero is if a == b). Therefore it can run for at most max(a,b)-1 steps

If you don't start with positive integers, then you'll loop forever. So make sure to avoid that.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.