On the continued fraction with rational partial quotients

Abstract

The Sorenson left shift 𝑘-ary gcd algorithm is one of the fastest greatest common divisor algorithms of two natural numbers. At the beginning a natural number 𝑘 > 2 is fixed, which is a parameter of algorithm. At each step we multiply smaller of two input numbers of current step, until it does not become greater of the second number. Then we calculate linear combination
between this number and the bigger of two input numbers. After that we replace the bigger of two input numbers by absolute value of the linear combination. At the end of the algorithm we obtain greatest common divisor of the two original numbers, which has been multiplied by some natural number. Spurious factor has appeared in the answer. We have proven estimation of the worst case of steps and obtained example of this case. Fixation of some endless sequence 𝐾 of natural numbers (each value is greater than 2) allows us to obtain the generalized Sorenson
left shift 𝑘-ary gcd algorithm. There at 𝑖-th step the value of 𝑘𝑖 ∈ 𝐾 is used instead of fixed parameter 𝑘. Both algorithms are completely coincide except this moment.

Continued fractions with rational partial quotients with left shift arise at applying of the generalized Sorenson left shift 𝑘-ary gcd algorithm to the ratio of two natural numbers 𝑎 and 𝑏. We can bind these continued fractions and polynomials of the special form, which called continuants. Numerator and denominator of such continued fractions can be expressed by
continuants. Formulas have been found that allow us to express continuants of the 𝑛-th order as some combination of continuants of a smaller order. Conditions were found at which a sequence of continuants of increasing order is strictly increasing. We also found conditions that allow unambiguous comparison of convergents of rational numbers that had performed by using continued fractions with rational partial quotients.