Abstract:
Continued fractions with rational partial quotients arise in a natural way in the course of applying any $k$-ary gcd algorithm to the ratio of natural numbers $a$, $b$. The paper deals with the problem of estimating the average length of continued fractions of four types with rational partial quotients obtained by using Sorenson's right and left-shift $k$-ary gcd algorithms. This problem is reduced to the problem of estimating the number of solutions of an equation of special form with constraints on the variables and, in two cases, the number of solutions of a system of equations with constrained variables must be estimated.
Keywords:$k$-ary gcd algorithm, continued fractions with rational partial quotients, continuants.
Fulltext:
PDF file (540 kB)
