2
$\begingroup$

I know that Fibonacci numbers show up in a special way in regard to the time it takes to solve Euclidean algorithm.

I am curious to know how to actually show how many steps it takes.

For example, how can we be sure that the Euclidean algorithm for computing $\operatorname{gcd}(F_{n+1},F_n)$ is bound by at least

$$K \log_2 F_n$$

for $n$ sufficient large, and suitable $K$?

My thoughts:

I know that the gcd of two consecutive Fibonacci numbers will be $1$ as they are co prime. And I also know the different expressions for Fibonacci numbers, in particular for the $n$th Fibonacci.

But I am not used to this type of problem.

I am particularly not sure how to involve the base 2 log and the constant in this problem So how would one approach this? Any help/ advice is very appreciated.

Thank you all

$\endgroup$
2
  • 1
    $\begingroup$ You can try to prove and use this identity $$ \gcd(F_{n}, F_{m}) = F_{\gcd(n,m)} $$ $\endgroup$ – MathGod Jan 14 '17 at 1:44
  • $\begingroup$ It may help to consider the most obvious case: that of consecutive Fibonacci numbers. Obviously one will have to step backward through the entire Fibonacci sequence to complete the Euclidian algorithm. $\endgroup$ – Wildcard Jan 14 '17 at 1:47
2
+50
$\begingroup$

The Fibonacci sequence represents a sort of "worse case" for the Euclidean algorithm. This occurs because, at each step, the algorithm can subtract $F_n\,\, $ only once from $F_{n+1} \,\,$. The result is that the number of steps needed to complete the algorithm is maximal with respect to the magnitude of the two initial numbers.

Applying the algorithm to two Fibonacci numbers $F {n}\,\, $ and $F_{n+1}\,\, $, the initial step is

$$ \gcd(F_{n},F_{n+1}) = \gcd(F_{n},F_{n+1}-F_{n}) = \gcd(F_{n-1},F_{n}) $$

The second step is

$$ \gcd(F_{n-1},F_{n}) = \gcd(F_{n-1},F_{n}-F_{n-1}) = \gcd(F_{n-2},F_{n-1}) $$

and so on. Proceding in this way, we need $n $ steps to arrive to $\gcd(F_{1},F_{2}) \,\,$ and to conclude that

$$ \gcd(F_{n},F_{n+1}) = \gcd(F_1,F_2) = 1$$

that is to say, two consecutive Fibonacci numbers are necessarily coprime.

Now it is well known that the growth rate of Fibonacci numbers, with respect to $n $, is exponential. In particular, $ F_n$ is asymptotic to

$${\displaystyle \varphi ^{n}/{\sqrt {5}}} $$

where

$$\varphi=\frac {1+\sqrt {5}}{2} \approx 1.61803$$

is the golden ratio. So, for $n $ sufficiently large, we have

$$n \approx \log_{\varphi} ( \sqrt {5}\,\, F_n) \\ = \log_{\varphi} ( F_n) + \frac {\log (5)}{2 \log (\varphi)} \approx \log_{\varphi} (F_n) $$

which tells us that the number of steps required to complete the Euclidean algorithm grows in a logarithmic manner with respect to $F_n\,\, $, and is bounded by the expression above. The same result can also be written using the logarithm in base $2$ as suggested by the OP:

$$n \approx \frac { \log_{2} F_n}{\log_{2} \varphi} =K \log_{2} F_n $$

where $$K=\frac {1}{\log_{2} \varphi}=\frac {\log {2}}{\log {\varphi}} \approx 1.4404... $$

$\endgroup$
3
  • $\begingroup$ Is there a way to do it without making assumptions about the limiting ratios and such? $\endgroup$ – PersonaA Jan 23 '17 at 2:06
  • $\begingroup$ Yes. If we do not consider the asymptotic behaviour of the Fibonacci ratio as already known, we can determine it. The most rapid way to do it is to note that if a limit $x $ of the ratio between consecutive terms exists, it must satisfy $$x^2F_{n}=xF_{n}+ F_{n}$$ and then $$ x^2-x-1=0$$ Solving this, the only positive solution is $x=(\sqrt {5}+1)/2$. Once determined this, we directly get that the sequence progressively tends to become a geometric progression with ratio $\varphi $, whose asymptote is $\varphi^n $. $\endgroup$ – Anatoly Jan 23 '17 at 6:40
  • $\begingroup$ @Anatoly Shouldn't the minimum number of steps to obtain $gcd(F_{n+1},F_n)$ be $n - 1$ , for large n. Continuing with the algorithm, $gcd(F_{n+1},F_n) = gcd(F_n,F_{n+1} - F_{n}) = gcd(F_n,F_{n-1}) = .... = gcd(F_{3},F_{2}) = gcd(2,1) = 1$ i.e. My point is you don't need to go $gcd(F_{2},F_{1})$ because already at the $(n-1)th$ step, you've obtained, 2 = 2*1 + 0, so your algorithm terminates. And since we're looking at the least number of steps, wouldn't it create problem? $\endgroup$ – reflexive Aug 23 '17 at 12:43
0
$\begingroup$

Theorem : number of steps in Euclidian algorithm $\le 5m$, where $m$ is number of digits in $min(a,b)$.

Proof : suppose we do all steps in Euclidian algorithm , so we have sequence of equations : $r_{i-1} = r_{i}q_{i} + r_{i+1}$. Consider $r_{n} = gcd(a,b) \ge 1$. Let's make an assumption : $r_{n-k} \ge \phi^{k}$, where $\phi = \frac{1 + \sqrt{5}}{2}$.

Base of induction : $r_{n} \ge \phi^{0} = 1$

Step : $r_{n-k-1} = r_{n-k}q_{n-k}+r_{n-k+1} \ge r_{n-k}+r_{n-k+1}\ge \phi^k + \phi^{k-1} = \phi^{k+1} $ - true.

So $r_1 \ge \phi^{n-1} $, but $10^{m-1} \le min(a,b) = r_{1} < 10^{m}$, so $m > (n-1)\ln\phi > (n-1)/5 $, so $n \le 5m$.


Now let's notice that inequality in proof could be equality for Fibonacci numbers.

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