Geodesic
Real number approximation by a rational number in the approximating $k$-ary algorithm
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 161 (2019) no. 2, pp. 250-262 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The best approximation by the irreducible fraction with the denominator not exceeding some specified value $n$ was investigated. The aim of this study was to find the fastest approximation algorithm that enables to accelerate the convergence of the $k$-ary algorithm for computing the greatest common divisor. The approximation based on Farey sequences was described; this method was considered using a quick exit condition, precomputation of the initial steps, and search in the Farey sequence built in advance. We also discussed the approximation with continued fractions and proposed an algorithm using a precomputation and continued fractions. The time and memory complexity of these algorithms were shown; these methods were compared with respect to running time and iterations amount. It was concluded that the approximation with the help of Farey sequences and precomputation is the fastest method, but the approximation with continued fractions has no additional memory demands.
Keywords: approximating $k$-ary algorithm, Farey sequence, continued fractions. 
@article{UZKU_2019_161_2_a5,
     author = {R. R. Enikeev},
     title = {Real number approximation by a rational number in the approximating $k$-ary algorithm},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {250--262},
     year = {2019},
     volume = {161},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2019_161_2_a5/}
}
TY  - JOUR
AU  - R. R. Enikeev
TI  - Real number approximation by a rational number in the approximating $k$-ary algorithm
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2019
SP  - 250
EP  - 262
VL  - 161
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZKU_2019_161_2_a5/
LA  - ru
ID  - UZKU_2019_161_2_a5
ER  - 
%0 Journal Article
%A R. R. Enikeev
%T Real number approximation by a rational number in the approximating $k$-ary algorithm
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2019
%P 250-262
%V 161
%N 2
%U http://geodesic.mathdoc.fr/item/UZKU_2019_161_2_a5/
%G ru
%F UZKU_2019_161_2_a5
R. R. Enikeev. Real number approximation by a rational number in the approximating $k$-ary algorithm. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 161 (2019) no. 2, pp. 250-262. http://geodesic.mathdoc.fr/item/UZKU_2019_161_2_a5/

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

[2] Jebelean T., “A generalization of the binary GCD algorithm”, Proc. 1993 Int. Symp. on Symbolic and Algebraic Computation, 1993, 111–116, ACM, N. Y. | DOI | Zbl

[3] Weber K., “The accelerated integer GCD algorithm”, ACM Transact. Math. Software, 21:1 (1995), 111–122 | DOI | MR | Zbl

[4] Ishmukhametov S., “An approximating $k$-ary GCD algorithm”, Lobachevskii J. Math, 37:6 (2016), 723–729 | DOI | MR | Zbl

[5] Charrier E., Buzer L., “Approximating a real number by a rational number with a limited denominator: A geometric approach”, Discrete Appl. Math., 157:16 (2009), 3473–3484 | DOI | MR | Zbl

[6] Hardy G. H., Wright E. M., An Introduction to the Theory of Numbers, Oxford Univ. Press, Oxford, 1975, 433 pp. | MR

[7] Vardi I., Computational Recreations in Mathematica, Addison-Wesley, Boston, 1991, 304 pp. | MR | Zbl

[8] Faddeev D. K., Lectures on Algebra, Nauka, M., 1984, 416 pp. (In Russian)

[9] Routledge N., “Computing Farey Series”, Math. Gazette, 92:523 (2008), 55–62 | DOI

[10] Levitin A. V., Algorithms. Introduction into the Development and Analysis, Vil'yams, M., 2006, 576 pp. (In Russian)

[11] Khinchin A. Ya., Continued Fractions, GIFML, M., 1961, 112 pp. (In Russian)