Analysis of the subtractive algorithm for greatest common divisors.
The sum of all partial quotients in the regular continued fraction expansions of m/n, for 1 </= m </= n, is shown to be 6pi(-2)n(ln n)(2) + O(n log n(log log n)(2)). This result is applied to the analysis of what is perhaps the oldest non-trivial algorithm for number-theoretic computations.
Yao
A C
AC
Computer Science Department, Stanford University, Stanford, California 94305.
Knuth
D E
DE