Сложение цепных дробей

[TelmanStud]

Доброго времени суток!
Пусть имеются две конечные цепные дроби одинаковой "глубины" $n$
$A=[a_{0};a_{1},a_{2},a_{3},\cdots,a_n ]=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+\ldots }}}}}}\;$
и
$B=[b_{0};b_{1},b_{2},b_{3},\cdots,b_n ]=b_{0}+{\cfrac {1}{b_{1}+{\cfrac {1}{b_{2}+{\cfrac {1}{b_{3}+\ldots }}}}}}\;$

Можно ли не сворачивая узнать неполные частные для $A+B=[c_0;c_1,c_2...,c_m]$?

Если, например складывать с самим собой, то всё просто $A+A=[2a_0;a_{1}/2,2a_2,a_{3}/2,...,a_n 2^{\text{sgn}(n)}]$.

[arseniiv]

TelmanStud в сообщении #1505562 писал(а):

Если, например складывать с самим собой, то всё просто $A+A=[2a_0;a_{1}/2,2a_2,a_{3}/2,...,a_n 2^{\text{sgn}(n)}]$.

Не так-то просто. Выйдет, что $2\cdot [1; 1, 2] = [2; \frac12, 4]$. Если надо иметь обычную цепную дробь, надо будет её ещё пересчитать (чтобы получить $[3; 3]$ или $[3; 2, 1]$).

[TelmanStud]

arseniiv
Спс. Однако проще допустить, что неполные частные не обязательно целые. А то там совсем какой то кошмар. Посмотрел в англоязычной литературе, что то тут есть
https://perl.plover.com/yak/cftalk/, но нормально разобрать не смог

[arseniiv]

Например про вычисление дробно-линейной функции $\frac{a + b X}{c + d X} =: f(a, b, c, d; X)$ там говорится такое:
• $f(a, b, c, d; [p; X]) = f(b, a + b p, d, c + d p; X)$,
• $f(a, b, c, d; X) = [q; f(c, d, a - c q, b - d q; X)]$, если $\lfloor a/c \rfloor = \lfloor b/d \rfloor = q$ (но обойдён стороной случай $c + dX\equiv 0$). Плюс тут стоит, как я понимаю, иметь в виду, что возможно и $q = +\infty$ (для чего понадобится как раз $c = d = 0$ и $a, b > 0$). Следует считать $[\ldots, +\infty] \equiv [\ldots]$.

Автор слайдов ссылается не только на материалы Госпера, но и на книгу Хинчина по цепным дробям — не смотрели, нет ли там?

Вообще идея замечательная и простая, и кстати прийти к идее считать сразу $\frac{a + bx + cy + dxy}{e + fx + gy + hxy} =: \tilde f(a, b, c, d, e, f, g, h; x, y)$ для произвольных коэффициентов не так уж сложно. В первой редакции моего предыдущего ответа, которую я не отправил, я пришёл к необходимости считать произведение, когда считаешь сумму. Если немного покрутить это в голове, можно дойти до более общей формы.

Когда мы преобразуем коэффициенты $a, \ldots, h$ в новые или выдаём очередной член в цепной дроби—результате, мы проверяем область значений всей функции $(x, y)\mapsto \tilde f(a, \ldots, h; x, y)$: достаточно ли она узка, чтобы знать очередной член или не убежала ли она в бесконечность (и тогда мы свободны). Преобразование же в противном случае довольно прямое — просто «вобрать» в коэффициенты знания об очередных членах аргументов—цепных дробей $X, Y$.

[TelmanStud]

arseniiv
Хотелось если Вам не сложно, пройти вдоль идей на примере конкретного сложения

[novichok2018]

Мне кажется, что никаких простых правил покомпонентного сложения не получится, что видно уже на простом примере обычных трёхэтажных дробей.

[arseniiv]

TelmanStud
Это можно, но надо сначала переписать алгоритм. И для удобства выписывания я тогда обозначу $\tilde f$ другой буквой, $F$.

Имеем:

(1) $F(a, b, c, d; e, f, g, h; [p; X], Y) = F(b, a + b p, d, c + d p; f, e + f p, h, g + h p; X, Y)$, если $\left| \frac bf - \frac ae \right| \geqslant \left| \frac cg - \frac ae \right|$;
(2) $F(a, b, c, d; e, f, g, h; X, [q; Y]) = F(c, d, a + c q, b + d q; g, h, e + g q, f + h q; X, Y)$, если $\left| \frac bf - \frac ae \right| \leqslant \left| \frac cg - \frac ae \right|$;
(3) $F(a, b, c, d; e, f, g, h; X, Y) = [r; F(e, f, g, h; a - e r, b - f r, c - g r, d - h r; X, Y)]$, если $a/e, b/f, c/g, d/h$ все имеют целую часть $r$, включая тот случай с бесконечностью ($a, b, c, d$ положительные, $e, f, g, h$ нули).

Тут надо дополнить (мне пришлось ещё немного почитать перед тем как уяснить), что если в условиях попадается ноль в знаменателях, но притом не во всех (когда мы закончим вычисления), шаги (1) или (2) стоит делать так, чтобы после них оказывалось меньше таких нулей. То есть если $h = 0$, то (если $g = 0$, лучше предпочесть (2)) и (если $f = 0$, лучше предпочесть (1)), иначе любое сгодится. Если $e = 0$, то (если $g = 0$, лучше предпочесть (1)) и (если $f = 0$, лучше предпочесть (2)), иначе снова подойдёт любое. И оставшиеся варианты аналогично, кроме варианта, когда они все равны нулю.

Найдём $[1; 1] + [1; 1, 1, 1] = F(0, 1, 1, 0; 1, 0, 0, 0; [1; 1], [1; 1, 1, 1])$. Сначала проверяем условие из (3) чтобы не делать лишних движений, но сразу видим, что ничего не будет, потому что $d/h$ вообще будет неопределённым, если считать. Проверим, пользоваться (1) или (2): $f = g = 0$, мы можем делать и то, и то. Сделаем (2).

$F(1, 0, 0 + 1, 1 + 0; 0, 0, 1 + 0, 0 + 0; [1; 1], [1; 1, 1]) = F(1, 0, 1, 1; 0, 0, 1, 0; [1; 1], [1; 1, 1])$.
Третий шаг опять не получится, и опять $h = 0$, но так как $g\ne 0$, предпочтём (1). [UPD: на самом деле если бы мы сделали (2), осталось бы только два нуля. Я неправильно там выше написал, но оставим как есть. Считать это всё руками очень утомительно, а код писать ради одного примера было бы довольно долго, плюс я бы не увидел пару случаев таким образом.]

$F(0, 1 + 0, 1, 1 + 1; 0, 0 + 0, 0, 1 + 0; [1], [1; 1, 1]) = F(0, 1, 1, 2; 0, 0, 0, 1; [1], [1; 1, 1])$.
С третьим шагом так и не повезёт и нам опять надо делать любой из (1), (2). Сделаем (1) и получим сюрприз: дробь $[1]$ кончится (превратится в $[] = +\infty$)! Но это на самом деле не страшно, так что сделаем пока этот шаг.

Так мы перейдём к $F(1, 1, 2, 3; 0, 0, 1, 1; [], [1; 1, 1])$. Теперь мы не можем делать (1), но мы могли бы продолжать дальше без особых проблем. Вместо этого мы можем избавиться от икса. Так как при $x\to\infty$ имеем $F(a, b, c, d; e, f, g, h; x, y) \to F(b, d; f, h; y)$ (предыдущая рассматривавшаяся функция), мы можем дальше продолжить более просто.

Значит теперь $F(1, 3; 0, 1; [1; 1, 1])$. Мы всё ещё не можем ничего выдать, так что тащим очередной элемент дроби-аргумента.

$F(3, 1 + 3; 1, 0 + 1; [1; 1]) = F(3, 4; 1, 1; [1; 1])$. Мы можем наконец-то выдать $\min(\lfloor \frac31 \rfloor, \lfloor \frac41 \rfloor) = 3$, хотя $\lfloor a/c \rfloor \ne \lfloor b/d \rfloor$. Ну я в таком явном виде это и не видел сформулированным, так что наверно мы ничего страшного не сделали. Выдавая 3, вычтем всё соответствующим образом; имеем теперь $[3; F(1, 1; 3 - 3, 4 - 3; [1; 1])] = [3; F(1, 1; 0, 1; [1; 1])]$.

Опять шаг (3) не выполним, берём очередной элемент. $[3; F(1, 2; 1, 1; [1])]$. Теперь мы можем выдать 1, придём к $[3; 1, F(1, 1; 1 - 1, 2 - 1; [1])] = [3; 1, F(1, 1; 0, 1; [1])]$. Тут повторится то, что мы делали только что, и выдастся ещё один раз 1: $[3; 1, 1, F(1, 1; 0, 1; [])]$. Тут мы опять можем заметить, что $F(a, b; c, d; y) \to b/d$ при $y\to\infty$. В итоге выйдет $[3; 1, 1, 1]$. Результат по крайней мере правильный, а то я успел испугаться и ошибок в выкладках, и того, что какой-то важный опущеный случай не удастся восстановить.

-- Пт фев 19, 2021 01:21:47 --

novichok2018
Ну референс же есть на алгоритмы, который сам ТС и нашёл. Там описание правда не из понятнейших, но я вот смог что-то посчитать, не знаю.

[TelmanStud]

arseniiv
Спс, буду разбираться!

[novichok2018]

Тогда хотелось бы увидеть, как это выглядит в простейшем случае для трёхэтажных дробей, если фиксировать в них порядок деления.
Дроби $a/b/c$, пусть первое деление считается последним по порядку, вторым. Или наоборот.

[arseniiv]

Это $[a; b, c] = a + \frac1{b + \frac1c}$?

Я выше расписал пример для $[1; 1] + [1; 1, 1, 1]$ и это вручную довольно муторно. Если заставить компьютер, это будет быстрее, но заставить в символьном виде будет очень много возни с реализацией. Мне как-то вот так без всякой мотивации, зачем это надо, если есть уже описания алгоритма, не хочется. Уж основу понять вообще просто, например.