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 number-theoretic computations.

Descriptors :   *Number theory, *Continued fractions, Computations, Algorithms

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE