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):

Report Date:

1975-09-01

Pagination or Media Count:

14.0

Abstract:

The sum of all partial quotients in the regular continued fraction expansions of mn, for 1 or m or n, is shown to be 6 Pi sup -2 nln n sup 2 On log nlog log n sup 2. This result is applied to the analysis of what is perhaps the oldest nontrivial algorithm for number-theoretic computations.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE