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?

  • 5
    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 http://en.wikipedia.org/wiki/Euclidean_algorithm#Average_number_of_steps.2012-02-15
  • 4
    ...and the worst case is when the inputs are two consecutive Fibonacci numbers.2012-02-15
  • 0
    I was sickened to the bone, when a friend showed me that an algorithm depending on (here $m,n$ are both **odd**) the recurrence relations (IIRC): $$gcd(2m,2n)=2gcd(m,n),$$ $$gcd(2m,n)=gcd(m,2n)=gcd(m,n)=gcd(min\{n,m\},|m-n|/2),$$ depending on the parity of the inputs has a better worst case complexity than Euclid, because here the size of the new input is alway at most one half of the previous, whereas in Euclid's Algorithm the size may only go down by a factor of the Golden Ratio (see the comment by J.M.)2012-02-15
  • 2
    @Jyrki: You mean the [binary GCD algorithm](http://en.wikipedia.org/wiki/Binary_GCD_algorithm)?2012-02-15
  • 4
    For every d, there are infinitely many pairs (m,n) such that gcd(m,n)=d. How do you define the average?2012-02-15
  • 0
    @Ilmari, that's the one. Thanks for the link (and the name of the algorithm).2012-02-15
  • 0
    @TsuyoshiIto, maybe to define it in the limit.2012-02-19
  • 2
    What do you mean by “define it in the limit”?2012-02-19
  • 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