
Accession Number : ADA017054
Title : Analysis of the Subtractive Algorithm for Greatest Common Divisors.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Personal Author(s) : Yao,Andrew C. ; Knuth,Donald E.
Report Date : SEP 1975
Pagination or Media Count : 14
Abstract : The sum of all partial quotients in the regular continued fraction expansions of m/n, for 1 < or = m < or = n, is shown to be 6 (Pi sup (2)) n(ln n) sup 2 + O(n log n(log log n) sup 2. This result is applied to the analysis of what is perhaps the oldest nontrivial algorithm for numbertheoretic computations.
Descriptors : *Number theory, *Continued fractions, Computations, Algorithms
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE