2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Сложение цепных дробей
Сообщение18.02.2021, 13:31 
Аватара пользователя


05/04/13
523
Доброго времени суток!
Пусть имеются две конечные цепные дроби одинаковой "глубины" $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)}]$.

 Профиль  
                  
 
 Re: Сложение цепных дробей
Сообщение18.02.2021, 16:41 
Заслуженный участник


27/04/09
28128
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]$).

 Профиль  
                  
 
 Re: Сложение цепных дробей
Сообщение18.02.2021, 18:05 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Сложение цепных дробей
Сообщение18.02.2021, 19:56 
Заслуженный участник


27/04/09
28128
Например про вычисление дробно-линейной функции $\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$.

 Профиль  
                  
 
 Re: Сложение цепных дробей
Сообщение18.02.2021, 21:26 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Сложение цепных дробей
Сообщение18.02.2021, 22:17 


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

 Профиль  
                  
 
 Re: Сложение цепных дробей
Сообщение18.02.2021, 23:20 
Заслуженный участник


27/04/09
28128
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
Ну референс же есть на алгоритмы, который сам ТС и нашёл. Там описание правда не из понятнейших, но я вот смог что-то посчитать, не знаю.

 Профиль  
                  
 
 Re: Сложение цепных дробей
Сообщение18.02.2021, 23:55 
Аватара пользователя


05/04/13
523
arseniiv
Спс, буду разбираться!

 Профиль  
                  
 
 Re: Сложение цепных дробей
Сообщение19.02.2021, 09:34 


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

 Профиль  
                  
 
 Re: Сложение цепных дробей
Сообщение19.02.2021, 15:25 
Заслуженный участник


27/04/09
28128
Это $[a; b, c] = a + \frac1{b + \frac1c}$?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group