Analysis of the subtractive algorithm for greatest common divisors

Area of Science:

• Number Theory
• Analytic Number Theory
• Computational Number Theory

Background:

• Continued fractions are fundamental in number theory, representing real numbers as sequences of integers.
• Understanding the properties of partial quotients is crucial for analyzing algorithms and number representations.

Purpose of the Study:

• To determine the asymptotic behavior of the sum of partial quotients for all fractions m/n up to n.
• To apply this result to the analysis of a classical number-theoretic algorithm.

Main Methods:

• Utilizing properties of regular continued fraction expansions.
• Applying analytic number theory techniques to estimate sums.

Main Results:

• The sum of partial quotients is asymptotically 6/pi^2 * n(ln n)^2 + lower-order terms.
• This provides a precise quantitative estimate for the growth of these sums.

Conclusions:

• The study provides a significant asymptotic formula for the sum of partial quotients.
• The findings offer new insights into the efficiency and behavior of fundamental number-theoretic algorithms.