16
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Have you tried actually running through the algorithm with pencil and paper? e.g., $\gcd(21, 34)$, $\gcd(34, 55)$, $\gcd(55, 89)$, $\gcd(89, 144)$, etc. With those last two examples, the result of the algorithm should be clear before you even begin since you already know $89$ is prime, so $55$ is clearly not a divisor and $144$ is not a multiple. $\endgroup$ – Bob Happ Oct 17 '17 at 21:23
  • $\begingroup$ Another thing you could do is write a little computer program that uses the algorithm and keeps track of how many steps each pair takes. $\endgroup$ – Bob Happ Oct 17 '17 at 21:25
13
$\begingroup$

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]$.

$\endgroup$
12
  • 1
    $\begingroup$ Very very nice explanation of this. $\endgroup$ – the_candyman Oct 17 '17 at 19:52
  • 1
    $\begingroup$ Beat me to it. Not surprised. $\endgroup$ – marty cohen Oct 17 '17 at 19:56
  • 2
    $\begingroup$ Technically impeccable, but probably not something the OP can grasp. $\endgroup$ – Yves Daoust Oct 17 '17 at 20:21
  • 1
    $\begingroup$ @YvesDaoust No, it is not. It is quite the opposite. The part that is omitted is precisely the part that contains all of the substance. This is more a comment than an answer. $\endgroup$ – Hellen Oct 17 '17 at 20:24
  • 1
    $\begingroup$ That is the same that was written obscuring things even more by using even more names. What is missing is the argument is to explain how if $b\leq a\leq F_n$ the algorithm for $a,b$ will stop not later than for $F_n,F_{n-1}$. $\endgroup$ – Hellen Oct 17 '17 at 20:31
7
$\begingroup$

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.$$

$\endgroup$
2
  • 2
    $\begingroup$ I don't think this proof is valid. Showing that you do the locally optimal decrease at each step does not imply that you end up with the globally optimal decrease along several steps --- there are lots of contexts in which this property does not hold. $\endgroup$ – Federico Poloni Oct 18 '17 at 6:33
  • $\begingroup$ @FedericoPoloni: that's right, my post is not meant to be a proof. $\endgroup$ – Yves Daoust Oct 18 '17 at 6:39
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

We note each step in the Euclidean algorithm (EA) is just an unravelling of the recurrence backwards starting $f_{n+2}=1\cdot f_{n+1}+f_{n}$ until, after $n$ steps we reach $f_{3}=2\cdot f_{2}+0$, by which $f_{1}=f_{2}=1$ is always the $\gcd$ of adjacent Fibonacci numbers: $(f_{n+1},f_{n})=1$.

\begin{align*} f_{n+2}&=1\cdot f_{n+1}+f_{n}\\ f_{n+1}&=1\cdot f_{n}+f_{n-1}\\ \dots\dots &\dots\dots \dots\dots\dots\\ f_{4}&=1\cdot f_{3}+f_{2}\\ f_{3}&=2\cdot f_{2} \end{align*} This shows the worst case scenario for the EA, since all partial quotients, bar the last, are $1$, and so it will take a maximum of $n$ steps. Indeed the least of such numbers that take a maximum of $n$ steps are adjacent Fibonacci numbers as we now show.

A theorem of Gabriel Lame shows the number of divisions required by the EA is at most $5$ times the number of digits in the smaller of the numbers. For this we need the inequality \begin{equation} f_{n+5}>10f_{n}\quad\text{ for $n=2,\,3,\,4,\dotsc$}\tag{1} \end{equation} This holds for $n=2$. For $n\geq3$ \begin{align*} f_{n+5}&=f_{n+4}+f_{n+3}=2f_{n+3}+f_{n+2}=3f_{n+2}+2f_{n+1}\\ &=5f_{n+1}+3f_{n}=8f_{n}+5f_{n-1} \end{align*} Since the Fibonacci sequence is not decreasing, we have $f_{n}=f_{n-1}+f_{n-2}\leq 2f_{n-1}$, which implies $2f_{n}\leq 4f_{n-1}$. Hence $f_{n+5}=8f_{n}+5f_{n-1}>8f_{n}+4f_{n-1}\geq10f_{n}$, which implies $f_{n+5}>10f_{n}$ as required. Now use induction for the general case: \begin{equation} f_{n+5k}>10^kf_{n}\quad\text{ for $n=2,\,3,\,4,\dotsc$; $k=1,\,2,\,3,\dotsc$}\tag{2} \end{equation} The $k=1$ case has been shown so assume true for some arbitrary $k\in\mathbb{N}$ and show for $k+1$: \begin{align*} f_{n+5(k+1)}&=f_{n+5+5k}=f_{n+4+5k}+f_{n+3+5k}=2f_{n+3+5k}+f_{n+2+5k}\\ &=3f_{n+2+5k}+2f_{n+1+5k} =5f_{n+1+5k}+3f_{n+5k}\\ &=8f_{n+5k}+5f_{n-1+5k} \end{align*} As before we have $f_{n+5k}=f_{n-1+5k}+f_{n-2+5k}\leq 2f_{n-1+5k}$, which implies $2f_{n+5k}\leq 4f_{n-1+5k}$. Hence \begin{align*} f_{n+5(k+1)}&=8f_{n+5k}+5f_{n-1+5k}>8f_{n+5k}+4f_{n-1+5k}\\ &\geq10f_{n+5k}>10\cdot10^k f_{n}=10^{k+1}f_{n} \end{align*} by hypothesis, which implies $f_{n+5(k+1)}>10^{k+1}f_{n}$ as required to complete the induction.

Now let $a_{0}$ and $a_{1}\in\mathbb{N}$, with $a_1<a_0$, and assume it takes $j$ divisions to find $(a_0,a_1)$ by the EA: \begin{align*} a_{0}&=q_1\cdot a_{1}+a_{2}\\ a_{1}&=q_2\cdot a_{2}+a_{3}\\ \dots&\dots\dots\dots \dots\dots\dots\\ a_{j-2}&=q_{j-1}\cdot a_{j-1}+a_{j}\\ a_{j-1}&=q_j\cdot a_{j} \end{align*} Now $q_j\neq1$ since then $a_{j-1}=a_{j}$. Thus $a_{j-1}=q_j\cdot a_{j}\geq2a_{j}\geq2=f_3$. Hence $a_{j-2}\geq a_{j-1}+a_{j}\geq f_3+f_2=f_4$, $a_{j-3}\geq a_{j-2}+a_{j-1}\geq f_4+f_3=f_5$, until we reach $a_1\geq f_{j}+f_{j-1}=f_{j+1}$ and $a_1\geq f_{j+1}+f_{j}=f_{j+2}$. If $j\geq5k+1$ then $a_1\geq f_{5k+2}>10^kf_2=10^k$ by $(2)$ and so has at least $k+1$ digits. Therefore if $a_1$ has $k$ digits, then $j\leq5k$, i.e., for $a_1$ having $k$ digits, at most $5k$ divisions are required in the EA as required. These inequalities show the claim above that adjacent Fibonacci numbers $f_{j+2}$ and $f_{j+1}$ are the least such to take $j$ steps to complete the EA and if it takes $j$ iterations to find $(a_0,a_1)$ as above, then $a_0\geq f_{j+2}$ and $a_1\geq f_{j+1}$.

Binet's closed form formula for the Fibonacci numbers is $$f_{n}=\frac{\varphi^{n}-\psi^{n}}{\varphi -\psi}=\frac{\varphi^{n}-\psi ^{n}}{\sqrt {5}}$$ where $$\varphi =\frac{1+\sqrt {5}}{2}\approx1.6180339887\dotsc \quad\text{and}\quad\psi =\frac{1-\sqrt {5}}{2}\approx-0.6180339887\dotsc$$ Binet's formula shows $f_n$ is asymptotic to $\varphi^n/\sqrt{5}$, which implies

\begin{equation}\label{eq:logfnsqrt5} n\approx \log_{\varphi}(f_n\sqrt{5})\approx \log_{\varphi}f_n \end{equation}

Hence if for integers $0<a<b$, the EA requires $n+1$ steps, then $b\geq f_{n+3}$, $a\geq f_{n+2}\geq \varphi^{n}$, then $n<\log_{\varphi}a$.

Since $f_n\sim \varphi^n/\sqrt{5}$, we also have the number of digits in $f_n$ approximately given as \begin{equation}\label{eq:digitsfn}\log_{10}\,f_n \approx n\log_{10}\varphi\approx0.20899n \end{equation} where we use base $10$ as we are in decimal.

Hence if the EA takes $n+1$ steps $0.2n<\log_{10}\varphi \log_{\varphi}a =\log_{10}a$. Thus, $n<5\log_{10}a$ implying the EA always needs less than $O(\text{#digits of $a$})$ divisions.

The EA is also known as the algorithm of continued fractions, since the $q_i$ from the EA make up the partial quotients of the fraction $a_0/a_1$'s continued fraction.

Let $a_0$ and $a_1$ be as before, having $j$ linear equations obtained via the EA. For $i=1,\dotsc, j-1$ let $$\frac{a_{i-1}}{a_{i}}=q_{i}+\frac{1}{\frac{a_i}{a_{i+1}}}\quad\text{and}\quad\frac{a_{j-1}}{a_j}=q_j$$ This gives a simple continued fraction $$\frac{a_0}{a_1}=[q_1;\,q_2,\dotsc,q_{j-1},\,q_j]$$ where all the numerators are $1$. Now $q_1$ is an integer, and since $a_{i-1}>a_i$, $q_2,\dotsc,q_j$ are natural numbers. Then on applying this to the Fibonacci sequence $$\frac{f_{n+1}}{f_{n}} =[1;\,1,\dotsc,1,\,1]\tag{3}$$ where there are $(n-1)$ $1s$ after the semicolon; note we could also write this as $$\frac{f_{n+1}}{f_{n}} =[1;\,1,\dotsc,1,\,2]$$ with $(n-3)$ $1s$ After the semicolon and a terminating $2$ in the continued fraction for $n\geq3$. We note the number of partial quotients in the continued fraction in $(3)$, and so in general for any two integers, gives the number of steps needed in the EA.

$\endgroup$
0
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2

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.