Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|cite|improve this question
Knuth has a detailed analysis in The Art of Computer Programming. From what I recall, the average time is of the same order of the worst case; only the constants are different. See…. –  lhf Feb 15 '12 at 10:41
...and the worst case is when the inputs are two consecutive Fibonacci numbers. –  J. M. is back. Feb 15 '12 at 10:55
@Jyrki: You mean the binary GCD algorithm? –  Ilmari Karonen Feb 15 '12 at 12:26
For every d, there are infinitely many pairs (m,n) such that gcd(m,n)=d. How do you define the average? –  Tsuyoshi Ito Feb 15 '12 at 12:59
What do you mean by “define it in the limit”? –  Tsuyoshi Ito Feb 19 '12 at 18:59

1 Answer 1

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

share|cite|improve this answer
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. –  marty cohen Aug 26 at 18:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.