Why are Fibonacci numbers bad for Euclid's Algorithm and how to derive this upper bound on number of steps needed in general?

Question

I want to ask two things.

The first is why are consecutive Fibonacci numbers the worst case for Euclid's algorithm? I keep seeing people say it in passing and I understand that it's really bad, but how do we know it's the worst?

The second question is about an upper bound on the number of applications of the division algorithm needed to compute the GCD of two distinct positive integers. I am given a hint that it will be of the form $c \log b + d$ when $c, d$ are constants and $b$ is the smaller of the two numbers you start with.

I have seen someone mention that it is $\frac{1}{2} \log b + 1$ but again, I don't know how to derive this and would very much appreciate a hint or push in the right direction.

Thank you in advance!

Answer 1

The number of steps required to compute $\gcd(a,b)$ is given by the length$^{(*)}$ of the continued fraction of $\frac{a}{b}$. It follows that the worst-case scenario for the Euclidean algorithm is given by the convergents of $\varphi=\frac{1+\sqrt{5}}{2}=[1;1,1,1,1,\ldots]$, i.e. by consecutive Fibonacci numbers.

(*) Explanation: assuming $a>b$, a step of the Euclidean algorithm brings the couple $(a,b)$ into the couple $(b,a\pmod{b})$. On the other hand, the Gauss map $x\mapsto \frac{1}{x-\lfloor x\rfloor}$ applied to $x=\frac{a}{b}$ acts in the exactly same way. It follows that the computation of $\gcd(F_{n+1},F_n)$ requires $n$ steps since it travels the convergents $[1],[1;1],[1;1,1],\ldots$ of $\frac{F_{n+1}}{F_n}$ in the opposite direction. Additionally, $\frac{F_{n+1}}{F_n}$ is the rational number $>1$ with a continued fraction having length $n$ and the least numerator/denominator: the terms of a continued fraction, with the only exception of the very first one, cannot be smaller than $1$. It follows that when considering all the continued fractions with the same length, the minimum of $\frac{a}{b}\to |a|+|b|$ is attained by $[0;1,1,1,\ldots]$.

Answer 2

Hint:

On every iteration, $(a,b)$ is replaced by $(b,a\bmod b)$. The worst case occurs when the decrease $a-b$ is the smallest, and this occurs when the integer quotient is $b/a=1$ (so that $a\bmod b=a-b$).

By its very definition, the Fibonacci sequence has this property at every step.

Now if $F_k\le b\le F_{k-1}$ for some $k$, the number of iterations for $n$ cannot exceed $F_k$ (the worst case).

From the Binet formula, $$F_k\approx\phi^k$$ and the bound is

$$k\approx\log_\phi n.$$

Answer 3

Let's say an input to the Euclidean algorithm is a pair $(a,b)$ of natural number $a,b\in\Bbb N$ (without zero) with $a> b$. Remember that for $a_0> b_0$, the algorithm proceeds via

$$a_{i+1}=b_i,\qquad b_{i+1}=a_i\text{ mod } b_i$$

and terminates after $k$ iterations when $b_k=0$. Let $A_k$ be the set of inputs for which the algorithm terminates in exactly $k$ steps. We show

Theorem. $A_k$ has a component-wise smallest element $(a,b)$, i.e. for all $(c,d)\in A_k$ we have $c\ge a$ and $d\ge b$.

I will give a proof, but let me first say the following: these component-wise smallest elements can be considered as the worst inputs to the Euclidean algorithm. Why? Because we expect smaller inputs to termiante earlier. But these specific minimal elements do not $-$ they are relatively small but need $k$ steps as all the other bigger elements in $A_k$ too. So these minimums are the worst when it comes to runtime relative to size.

Proof.

The proof goes by induction. It is easy enough to see that $A_1=\{(ka,a)\mid a,k\in\Bbb N,k\ge 2\}$. Then $A_1$'s smallest element is $(2,1)$.

It is also straight forward to see that if $(a,b)\in A_k$, then $(a+b,a)\in A_{k+1}$. I claim that if $(a,b)$ is minimal in $A_k$, then $(a+b,a)$ is minimal in $A_{k+1}$.

Let's show this by contradiction. Assume there is an element $(c,d)\in A_{k+1}$ with $c<a+b$ or $d<a$. We can exclude the last case, because one iteration of the Euclidean algorithms would generate $(d,c\text{ mod } d)\in A_k$ for which $(a,b)$ is not smaller now, in contradiction to its choice. So we have $d\ge a$ but $c<a+b$. We also see that $(c\text{ mod } d)\ge b$, which is equivalent to $c-kd\ge b$ for some $k\in\Bbb N$, especially $c-d\ge b$. But now

$$c<a+b\le d+(c-d)=c.$$

Contradiction. $\quad\square$

So we have a worst element in $A_k$ in some precise sense. And if you follow the construction of these element in the proof, you can see that they follow the generation rule of the Fibonacci numbers.

If you are familiar with the Fibonacci numbers $F_k$, then you probably know that $F_k$ grows exponentially like $\phi^k$ where $\phi$ is the golden ration $\phi\approx 1.618...$. So this construction yields an input pair with elements of minimum size $\sim\phi^k$ in $A_k$ which terminates after $k$ steps. Turn this around and you have that in the worst case for an input pair with elements of minimum size $s$, the Euclidean algorithm terminates after $\sim \log_\phi s$ steps.

Answer 4

A brute force run shows that the maximum number of iterations is indicated by the ordinality of the first Fibonacci number greater than the larger number of the pair subjected to Euclid's Algorithm. For example, for the numbers $(1000,x)$, the next Fibonacci number is $1597$ and it is the $15^{th}$ or $16^{th}$ Fibonacci number depending on where you begin the series, so the maximum number of iterations is $15$ or $16$ assuming $x$ is smaller than $1000$. (Note: If the larger number is entered second, the iteration count is one higher.)

Here is a sample run in which the "count" and GCD numbers are displayed $\textbf{only}$ when the current iteration count for a pair is greater than the previous "largest count". It took $\approx 3.2$ hours of CPU time using interpretive BASIC. I'm sure it would take less time with math-specific languages.

 enter limit? 100000
 iterations( 1 )    GCD( 2 , 1 ) = 1 
 iterations( 2 )    GCD( 3 , 2 ) = 1 
 iterations( 3 )    GCD( 5 , 3 ) = 1 
 iterations( 4 )    GCD( 8 , 5 ) = 1 
 iterations( 5 )    GCD( 13 , 8 ) = 1 
 iterations( 6 )    GCD( 21 , 13 ) = 1 
 iterations( 7 )    GCD( 34 , 21 ) = 1 
 iterations( 8 )    GCD( 55 , 34 ) = 1 
 iterations( 9 )    GCD( 89 , 55 ) = 1 
 iterations( 10 )   GCD( 144 , 89 ) = 1 
 iterations( 11 )   GCD( 233 , 144 ) = 1 
 iterations( 12 )   GCD( 377 , 233 ) = 1 
 iterations( 13 )   GCD( 610 , 377 ) = 1 
 iterations( 14 )   GCD( 987 , 610 ) = 1 
 iterations( 15 )   GCD( 1597 , 987 ) = 1 
 iterations( 16 )   GCD( 2584 , 1597 ) = 1 
 iterations( 17 )   GCD( 4181 , 2584 ) = 1 
 iterations( 18 )   GCD( 6765 , 4181 ) = 1 
 iterations( 19 )   GCD( 10946 , 6765 ) = 1 
 iterations( 20 )   GCD( 17711 , 10946 ) = 1 
 iterations( 21 )   GCD( 28657 , 17711 ) = 1 
 iterations( 22 )   GCD( 46368 , 28657 ) = 1 
 iterations( 23 )   GCD( 75025 , 46368 ) = 1 

BASIC is considered unsophisticated these days but it is free and easier to learn that PYTHON and others. Here is the program that ran the test above.

  100 print "enter limit";
  110 input l1
  120 c9 = 0
  130 for i1 = 1 to l1
  140    for i2 = 1 to i1-1
  150 c1 = 0
  160 x1 = i1
  170 x2 = i2
  180 r1 = x1 mod x2
  190 c1 = c1+1
  200 if r1 > 0
  210    x1 = x2
  220    x2 = r1
  230 goto 180
  240 endif
  250 if c1 > c9
  260    c9 = c1
  270    print "iterations( " c1 ")  ",;
  280    print "GCD( " i1 ", " i2 ") = " x2
  290 endif
  300   next i2
  310 next i1

Answer 5

You can prove this using induction on the number of gcd() calls.

To prove: If a pair (a,b) takes n steps to compute the gcd, then

1. a >= F_(k+2)
2. b >= F_(k+1) With one assumption a >= b

Base case n = 1, the lemma is true.

Consider the lemma to be true for n = k - 1, k > 1

Let a pair (a,b) be such that it takes k steps to compute the gcd. Hence (b, a mod b) will take k - 1 steps. Thus b >= F_(k+1) ... by hypothesis And a mod b >= F_(k)

Now, a = b×q + a mod b >= b + a mod b >= F_(k+1) + F_(k) >= F(k+2)

Hence we have proven that consequentive fibonacci numbers are the worst case. More specifically, they are the least of the numbers to take a certain arbitrary number of steps.