The Average Running Time Of Euclid Algorithm?

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?

-
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 en.wikipedia.org/wiki/…. – lhf Feb 15 '12 at 10:41
...and the worst case is when the inputs are two consecutive Fibonacci numbers. – J. M. 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

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