Приближение вещественного числа рациональным в аппроксимирующем k-арном алгоритме

Р.Р. Еникеев
Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия

Полный текст PDF

DOI: 10.26907/2541-7746.2019.2.250-262

Для цитирования: Еникеев Р.Р. Приближение вещественного числа рациональным в аппроксимирующем k -арном алгоритме // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2019. – Т. 161, кн. 2. – С. 250–262. – 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)

Аннотация

Исследована задача нахождения наилучшего приближения вещественного числа несократимой дробью, знаменатель которой не превосходит заданного значения n. Цель работы состояла в нахождении самого быстрого метода аппроксимации, что позволит ускорить сходимость аппроксимирующего k-арного алгоритма вычисления наибольшего общего делителя. Описано приближение с помощью рядов Фарея, рассмотрены методы ускорения этого алгоритма с использованием условия быстрого выхода из цикла, предвычисления начальных шагов алгоритма и поиска по заранее построенному ряду. Рассмотрена также аппроксимация цепными дробями и разработан метод, который использует их и предвычисленные начальные шаги, полученные с помощью рядов Фарея. Получены оценки сложности этих методов и проведено сравнение алгоритмов по количеству итераций и времени выполнения. В результате сравнения показано, что приближение с помощью рядов Фарея и предвычислением показывает лучшее время, а среди алгоритмов, не использующих дополнительную память, – метод, основанный на цепных дробях. Полученные результаты позволяют выбрать подходящий алгоритм в зависимости от требований, предъявляемых к программному продукту, реализующему приближение вещественного числа.
Ключевые слова: аппроксимирующий k-арный алгоритм, ряды Фарея, цепные дроби

Литература

1. Sorenson J. Two fast GCD algorithms // J. Algorithms. – 1994. – V. 16, No 1. – P. 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. – N. Y.: ACM, 1993. – P. 111–116. – doi: 10.1145/164081.164102.
3. Weber K. The accelerated integer GCD algorithm // ACM Transact. Math. Software. – 1995. – V. 21, No 1. – P. 111–122. – doi: 10.1145/200979.201042.
4. Ishmukhametov S. An approximating k -ary GCD algorithm // Lobachevskii J. Math. – 2016. – V. 37, No 6 – P. 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. – V. 157, No 16 – P. 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. Фаддеев Д.К. Лекции по алгебре. – М.: Наука, 1984. – 416 с.
9. Routledge N. Computing Farey Series // Math. Gazette. – 2008. – V. 92, No 523. – P. 55–62. – doi: 10.1017/S002555720018252X.
10. Левитин А.В. Алгоритмы. Введение в разработку и анализ. – М.: Вильямс, 2006. –
576 с.
11. Хинчин А.Я. Цепные дроби. – М.: ГИФМЛ, 1961. – 112 с.

Поступила в редакцию
07.06.18

Еникеев Разиль Радикович, ассистент кафедры системного анализа и информационных технологий
Казанский (Приволжский) федеральный университет
ул. Кремлевская, д. 18, г. Казань, 420008, Россия
E-mail: renikeev@kpfu.ru

Контент доступен под лицензией Creative Commons Attribution 4.0 License.