1
$\begingroup$

I have been reading Stark, H. (1978). An Introduction to Number Theory and there is a section where the author proves that the algorithm must eventually reach $0$.

If we are looking for GCD($a, b$) and $a > b$ then the number of steps $k$ needed to reach $0$ is always $k < a$. Worst case being that $k = a - 1$ and at every step the remainder is always reduced by $1$ (though that would rarely if ever happen). So that has to be the maximum number of steps needed for the algorithm to terminate.

Now I have seen some other calculations with $a + b$ being the upper bound or some stuff with Fibonacci numbers. Do such things calculate the maximum number of steps or something else because I am pretty sure that the maximum number of steps is less than $a$. I may be wrong. Can anyone provide some insight into this?

EDIT

Confusion arises from the following answer where the user says that the upper bound on the number of steps is the sum of $a, b$ which is too large. Number of steps should be less than $a$.

Quote from the book:

it is clear that, sooner or later, some $r_k$ will equal $0$ and, in fact, since each $r_k$ is at least one smaller than the $r_k$ before it, we will come to a $r_k = 0$ with $k < a$.

$\endgroup$
  • $\begingroup$ If $a>b,$ the maximum remainder is $b-1$ not $a-1$. Two consecutive Fibonacci numbers gives the worst-case performance of the algorithm. $\endgroup$ – saulspatz Mar 13 at 13:34
  • $\begingroup$ $k$ is not maximum remainder, it is maximum number of steps for the algorithm to terminate. Maximum number of steps is $k$ with $k < a$. And worst case $k = a - 1$. $\endgroup$ – Michael Munta Mar 13 at 14:10
  • $\begingroup$ How can that be? If the next quotient is $b_1$ you are saying that there are no more than $b-2$ steps remaining. Together with the first division, that makes $b-1$. $\endgroup$ – saulspatz Mar 13 at 14:24
  • $\begingroup$ I am saying hypothetically that the number of divisions in the algorithm for some $a, b$ will never be larger than $a$, that should be obvious. $\endgroup$ – Michael Munta Mar 13 at 14:27
  • $\begingroup$ Yes, of course it's obvious. I'm saying it's a very weak statement. $\endgroup$ – saulspatz Mar 13 at 14:30
2
$\begingroup$

The right answer is given by that Fibonacci number "stuff".

The decrease will be the slowest when every quotient is one, i.e. when the divisions are mere subtractions. And the longest when the $\gcd$ is one. If we backtrack from $a=1,b=1$, doing additions only, we get the Fibonacci sequence. It is in fact possible to show that if $\min(a,b)$ doesn't exceed $F_m$ at a given step, it cannot exceed $F_{m-1}$ at the next.

As $F_m\sim\phi^m$, the growth is exponential, and conversely, the maximum number of steps from a given $n$ is logarithmic.

$\endgroup$
  • $\begingroup$ @MichaelMunta: the number of steps is $O(\log n)$, this is what matters. $\endgroup$ – Yves Daoust Mar 13 at 15:13
  • $\begingroup$ Well I have only stated in my question that number of steps will really never go above $k = a - 1$ just as the author of the book has written (tightness of that value was never the subject). Though I would still like if you provided an example for the middle paragraph in your answer. $\endgroup$ – Michael Munta Mar 14 at 15:39
  • $\begingroup$ Can you tell me what this expression $F_m\sim\phi^m$ means, specifically the relation symbol in the middle? Suppose $m = 5$, then $5 \sim 11,0890...$ $\endgroup$ – Michael Munta Mar 16 at 11:45
  • $\begingroup$ @MichaelMunta: in this context, "grows like". The ratio of two successive Fibonacci numbers quickly tends to the Golden Ratio. The key point is exponential growth. $\endgroup$ – Yves Daoust Mar 16 at 12:38
  • $\begingroup$ @MichaelMunta: please stop the harrassment. If you don't like my answer, move on. $\endgroup$ – Yves Daoust Mar 16 at 13:53

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.