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
Voir la notice du chapitre de livre provenant de la source Math-Net.Ru
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},
publisher = {mathdoc},
volume = {161},
number = {2},
year = {2019},
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 PB - mathdoc 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 %I mathdoc %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/