О цепных дробях с рациональными неполными частными

Аннотация

Алгоритм Соренсона с левым сдвигом – один из быстрых алгоритмов вычисления наибольшего общего делителя двух натуральных чисел. В начале его работы фиксируется натуральное число 𝑘 > 2, которое является параметром. На каждом шаге алгоритма выполняется поиск линейной комбинации входных чисел текущего шага, причем наименьшее из них предварительно домножается на параметр 𝑘, пока не начнет превосходить наибольшего. После этого наибольшее число замещается абсолютным значением линейной
комбинации. Результатом работы алгоритма является наибольший общий делитель исходных чисел, умноженный на некоторое число, называемое побочным множителем. Для
алгоритма Соренсона была доказана оценка числа шагов в худшем случае, приведен пример. Фиксация некоторой бесконечной последовательности 𝐾 натуральных чисел больших
двух позволяет получить обобщенный алгоритм Соренсона. В нем на каждом шаге вместо числа 𝑘 будет задействовано определенное значение параметра 𝑘𝑖 ∈ 𝐾, соответствующее текущему шагу алгоритма. В остальном алгоритмы полностью совпадают друг с другом.
Цепные дроби с рациональными неполными частными c левым сдвигом возникают в ходе применения к отношению натуральных чисел 𝑎, 𝑏 обобщенного 𝑘-арного алгоритма Соренсона с левым сдвигом. С ними связаны особые формы континуантов, то есть многочленов, при помощи которых выражаются числитель и знаменатель подходящей дроби. Для таких континуантов найдены формулы, позволяющие представить континуант 𝑛-го порядка в виде некоторой комбинации континуантов меньших порядков. Были найдены условия при которых последовательность континуантов увеличивающегося порядка является строго возрастающей. Также были найдены условия, при которых приближения рациональных чисел, выполненные при помощи цепных дробей с рациональными неполными частными, можно однозначно сравнивать.