Geodesic
On the continued fraction with rational partial quotients
Čebyševskij sbornik, Tome 25 (2024) no. 2, pp. 43-66 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The Sorenson left shift $k$-ary gcd algorithm is one of the fastest greatest common divisor algorithms of two natural numbers. At the beginning a natural number $k>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 $K$ of natural numbers (each value is greater than 2) allows us to obtain the generalized Sorenson left shift $k$-ary gcd algorithm. There at $i$-th step the value of $k_i \in K$ is used instead of fixed parameter $k$. 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 $k$-ary gcd algorithm to the ratio of two natural numbers $a$ and $b$. 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 $n$-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.
Keywords: continued fraction, greatest common divisor
Mots-clés : continuant, Diophantine approximation. 
@article{CHEB_2024_25_2_a3,
     author = {D. A. Dolgov},
     title = {On the continued fraction with rational partial quotients},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {43--66},
     year = {2024},
     volume = {25},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2024_25_2_a3/}
}
TY  - JOUR
AU  - D. A. Dolgov
TI  - On the continued fraction with rational partial quotients
JO  - Čebyševskij sbornik
PY  - 2024
SP  - 43
EP  - 66
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CHEB_2024_25_2_a3/
LA  - ru
ID  - CHEB_2024_25_2_a3
ER  - 
%0 Journal Article
%A D. A. Dolgov
%T On the continued fraction with rational partial quotients
%J Čebyševskij sbornik
%D 2024
%P 43-66
%V 25
%N 2
%U http://geodesic.mathdoc.fr/item/CHEB_2024_25_2_a3/
%G ru
%F CHEB_2024_25_2_a3
D. A. Dolgov. On the continued fraction with rational partial quotients. Čebyševskij sbornik, Tome 25 (2024) no. 2, pp. 43-66. http://geodesic.mathdoc.fr/item/CHEB_2024_25_2_a3/

[1] Morier-Genoud S., Ovsienko V., “Farey Boat: Continued Fractions and Triangulations, Modular Group and Polygon Dissections”, Jahresber. Dtsch. Math., 121 (2019), 91–136 | DOI | MR | Zbl

[2] Çanakçı İ., Schiffler R., “Snake graphs and continued fractions”, European Journal of Combinatorics, 86 (2020) | MR

[3] Sorenson J., “Two Fast GCD Algorithms”, J. of Algorithms, 16:1 (1994), 110–144 | DOI | MR | Zbl

[4] Morrison D., Angel E., “Speeding Up Bresenham's Algorithm”, IEEE Computer Graphics and Applications, 11:6 (1991), 16–17 | DOI

[5] Zhang Z., “Finding $c_3$-strong pseudoprimes”, Mathematics of computation, 74:250 (2004), 1009–1024 | DOI | MR

[6] Xiao L., Xia X. -G., Wang W., “Multi-Stage Robust Chinese Remainder Theorem”, IEEE Transactions on Signal Processing, 62:18 (2014), 4772–4785 | DOI | MR | Zbl

[7] Weber, K., “The Accelerated Integer GCD Algorithm”, ACMTrans.Math. Software, 21:1 (1995), 111–122 | DOI | MR | Zbl

[8] Dolgov, D., “GCD calculation in the search task of pseudoprime and strong pseudoprime numbers”, Lobachevskii J Math., 37:6 (2016), 734–739 | DOI | MR | Zbl

[9] Dolgov, D. A., “An extended Jebelean-Weber-Sedjelmaci GCD algorithm”, Chebyshevskii Sbornik, 19:2 (2018), 421–431 (in russian) | DOI | Zbl

[10] Dolgov D. A., “K-arnyi algoritm vychisleniya NOD bez pobochnykh mnozhitelei”, XVI Mezhdunarodnaya konferentsiya «Algebra, teoriya chisel i diskretnaya geometriya: sovremennye problemy, prilozheniya i problemy istorii» (Tula, 2019), 2019, 162–165

[11] Karatsuba, A. A., Principles of Analytic Number Theory, Nauka, M., 1983 | MR

[12] Jebelean T., A generalization of the binary GCD algorithm, ISAAC (Kiev, 1993), 1–5 | Zbl

[13] Stein J., “Computational problems associated with Racah algebra”, J. Comp. Phys., 1:3 (1967), 397–405 | DOI | Zbl

[14] Dolgov, D. A., “Continuants of continued fractions with rational incomplete quotients”, Diskr. Mat., 34:3 (2022), 34–51 (in russian) | DOI

[15] Straustrup B., The C++ Programming Language, Addison-Wesley Professional, 2013

[16] Bosma W., Kraaikamp C., Hommersom S., Keune M., Kooloos C., van Loon W., Loos R., Omiljan E., Popma G., Venhoek D., Zwart M., Continued fractions, , 2012 https://www.math.ru.nl/b̃osma/Students/CF.pdf

[17] Muir T., A Treatise on the Theory of Determinants, Dover Publications, 1960, 766 pp. | MR