7
$\begingroup$

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$?

It seems very hard to deduce from the recurrence $T(m,n) = T(n, m \bmod n)+1$.

Any better ideas?

  • 1
    @J.M. The numbers need not be Fibonacci numbers; you can seed the recurrence $a_n = a_{n - 1} + a_{n - 2}$ with any initial values and consecutive pairs of this sequence will perform just as badly.2012-02-29

1 Answers 1

2

The number of steps needed to compute $\gcd(m,n)$ is given by the length of the continued fraction of $\frac{m}{n}$, hence the worst case is to compute the $\gcd$ of two consecutive Fibonacci numbers (since $\frac{F_{n+1}}{F_n}=[1;1,\ldots,1]$) and an upper bound for the number of steps involved is: $ 1+\frac{\log(\max(m,n))}{\log\varphi} $ where $\varphi$ is the golden ratio $\varphi=\frac{1+\sqrt{5}}{2}$.

  • 0
    I have read every page of all three volumes of Knuth. I remember that. Wow is there a lot of stuff rattling around inside my head.2015-08-26