Analysis of the Subtractive Algorithm for Greatest Common Divisors.

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.

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1975
Accession Number
ADA017054

Entities

People

  • Andrew C. Yao
  • Donald Knuth

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Mathematical Analysis
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Regression Analysis.