Real number approximation by a rational number in the approximating k-ary algorithm
R.R. Enikeev
Kazan Federal University, Kazan, 420008 Russia
E-mail: renikeev@kpfu.ru
Received June 7, 2018
DOI: 10.26907/2541-7746.2019.2.250-262
For citation: Enikeev R.R. Real number approximation by a rational number in the approximating k-ary algorithm. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2019, vol. 161, no. 2, pp. 250–262. doi: 10.26907/2541-7746.2019.2.250-262. (In Russian)
Abstract
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
References
1. Sorenson J. Two fast GCD algorithms. J. Algorithms, 1994, vol. 16, no. 1, pp. 110–144. doi: 10.1006/jagm.1994.1006.
2. Jebelean T. A generalization of the binary GCD algorithm. Proc. 1993 Int. Symp. on Symbolic and Algebraic Computation. New York, ACM, 1993, pp. 111–116. doi: 10.1145/164081.164102.
3. Weber K. The accelerated integer GCD algorithm. ACM Trans. Math. Software, 1995., vol. 21, no. 1, pp. 111–122. doi: 10.1145/200979.201042.
4. Ishmukhametov S. An approximating k-ary GCD algorithm. Lobachevskii J. Math., 2016, vol. 37, no. 6, pp. 723–729. doi: 10.1134/S1995080216060147.
5. Charrier E., Buzer L. Approximating a real number by a rational number with a limited denominator: A geometric approach. Discrete Appl. Math., 2009, vol. 157, no. 16, pp. 3473–3484. doi: 10.1016/j.dam.2009.03.005.
6. Hardy G.H., Wright E.M. An Introduction to the Theory of Numbers. Oxford, Oxford Univ. Press, 1975. 433 p.
7. Vardi I. Computational Recreations in Mathematica. Boston, Addison-Wesley, 1991. 304 p.
8. Faddeev D.K. Lektsii po algebre [Lectures on Algebra]. Moscow, Nauka, 1984. 416 p. (In Russian)
9. Routledge N. Computing Farey Series. Math. Gazette, 2008, vol. 92, no. 523, pp. 55–62. doi: 10.1017/S002555720018252X.
10. Levitin A.V. Algoritmy. Vvedenie v razrabotku i analiz [Algorithms. Introduction into the Development and Analysis]. Moscow, Vil'yams, 2006. 576 p. (In Russian)
11. Khinchin A.Ya. Tsepnye drobi [Continued Fractions]. Moscow, GIFML, 1961. 112 p. (In Russian)
The content is available under the license Creative Commons Attribution 4.0 License.
