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

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