1

Im trying to show that the following algorithm terminates when a,b are larger than zero. I tried it firstly by complete induction for (a,n) when n is any number but got stuck at the case that n > a. Is there other way to show it? thanks

while (a!=b) {
        if (a>b) 
            a=a-b;
        else
            b=b-a;
     }
Yoav Cohen
  • 125
  • Possible duplicate of Termination state while subtracting two numbers – Smylic Mar 22 '17 at 07:34
  • Im looking only for termination not correctness, any way can you clarify his answer? thank you – Yoav Cohen Mar 22 '17 at 07:38
  • This is not mathematics but programming and probably even language dependent and definitely type dependent what the code would do. I would recommend a migration to one of the programming exchanges. – mathreadler Mar 22 '17 at 14:49
  • @mathreadler This question definitely has a mathematical aspect to it. It can be proved rigorously what the behavior of the code will be. Yes, it's cast as code, which it need not be. Perhaps the OP may consider posting the worded version of this question or one which makes use of only mathematical notation. Though I don't see that this would be necessary. – ThisIsNotAnId Mar 22 '17 at 15:25
  • 1
    @mathreadler On second thought, I want to agree with your concern, but only as far as the implementation of the algorithm goes. There's code bugs to watch out for and architecture instruction set fault tolerance among other things. That part of the question should definitely be on StackOverflow, theoretical CS, or other related site. – ThisIsNotAnId Mar 22 '17 at 15:51
  • The question is phrased about an "algorithm" terminating. The OP has tried to use induction to prove it. The fact that the algorithm is presented as a simple program in a language that is not fully specified is as much a reason to put this topic on hold than if it was written in bad English. – Ingix Mar 22 '17 at 16:15
  • @Ingix I truly believe this exact question can be cast as a combinatorics, number theory, or simple algebra problem. Agreed, it being presented as a coding question is confusing and should be avoided on Math.SE, and will prevent others who have no knowledge of programming languages from answering; this question has a strong mathematical backdrop to it. If anything, an answer in purely mathematical terms is possible. Otherwise, I don't see why this question should be understood as unclear. And the fact that the "algorithms" tag even exists here goes to show that there is good context. – ThisIsNotAnId Mar 22 '17 at 16:44

1 Answers1

0

Each iteration changes only one variable $a$ or $b$. If $a$ is changed, $a_{new}> 0$ is obvious. If $b$ is changed, $b_{new} \ge 0$ is obvious, but it follows $b_{new} > 0$ because equality happens only when $a=b$ and in this case the loop would have stopped.

This means after each loop iteration the values of $a$ and $b$ are again both positive. But the value of their sum has decreased, it was $a_{old}+b_{old}$ before but is now $a_{old}$ (if $a$ changed) or $b_{old}$ (if $b$ changed). So after each loop iteration, we get a smaller (but still positive) value as the sum $a+b$. This means the loop must stop.

Ingix
  • 14,494