Chebyshevskii Sbornik
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Chebyshevskii Sb.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Chebyshevskii Sbornik, 2024, Volume 25, Issue 2, Pages 43–66
DOI: https://doi.org/10.22405/2226-8383-2024-25-2-43-66
(Mi cheb1418)
 

On the continued fraction with rational partial quotients

D. A. Dolgov

Institute of Computational Mathematics and Information Technologies, Kazan (Volga Region) Federal University (Kazan)
References:
Abstract: 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, continuant, greatest common divisor, Diophantine approximation.
Funding agency Grant number
Ministry of Science and Higher Education of the Russian Federation
This paper has been supported by the Kazan Federal University Strategic Academic Leadership Program (“PRIORITY-2030”).
Received: 08.01.2024
Accepted: 28.06.2024
Document Type: Article
UDC: 511.41
Language: Russian
Citation: D. A. Dolgov, “On the continued fraction with rational partial quotients”, Chebyshevskii Sb., 25:2 (2024), 43–66
Citation in format AMSBIB
\Bibitem{Dol24}
\by D.~A.~Dolgov
\paper On the continued fraction with rational partial quotients
\jour Chebyshevskii Sb.
\yr 2024
\vol 25
\issue 2
\pages 43--66
\mathnet{http://mi.mathnet.ru/cheb1418}
\crossref{https://doi.org/10.22405/2226-8383-2024-25-2-43-66}
Linking options:
  • https://www.mathnet.ru/eng/cheb1418
  • https://www.mathnet.ru/eng/cheb/v25/i2/p43
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024