Analysis of the subtractive algorithm for greatest common divisors
- 1 December 1975
- journal article
- research article
- Published by Proceedings of the National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 72 (12) , 4720-4722
- https://doi.org/10.1073/pnas.72.12.4720
Abstract
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.This publication has 0 references indexed in Scilit: