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