16
$\begingroup$

I thought about continued fractions as a cool way to represent numbers, but also about the fact they are difficult to treat because standard algebraic operations like addition and multiplication don't work on them in a simple way. My question is: do there exist some simple and interesting operations that have a regular behavior with respect to the normal form of a continued fraction? For example, does there exist a simple $\circ$, $?$ or $*$ that satisfies

$$ a = [a_0; a_1, a_2 \, ... \, a_n] \\ b = [b_0; b_1, b_2 \, \ldots \, b_n] \\ a \circ b = [a_0 \circ b_0; a_1 \circ b_1, a_2 \circ b_2 \, \ldots \, a_n \circ b_n] $$ or $$ a \,?\, b = [a_0 + b_0; a_1 + b_1, a_2 + b_2 \, \ldots \, a_n + b_n] $$ or $$ *a = [2 a_0; 2 a_1, 2 a_2 \, \ldots \, 2 a_n] $$

Note that $ [a_0; a_1, a_2 \, \ldots \, a_n] $ can represent:

$$ a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots a_{n-1} + \cfrac{1}{a_n}}}} $$ or $$ a_0 + \cfrac{m_1}{a_1 + \cfrac{m_2}{a_2 + \cfrac{m_3}{\ddots a_{n-1} + \cfrac{m_{n}}{a_n}}}} $$

$\endgroup$
2
  • 5
    $\begingroup$ Continued fractions are not a good way to represent rational numbers if you're interested in adding or multiplying them. They're a good way to represent rational numbers if you're interested in applying certain fractional linear transformations to them (namely those of the form $z \mapsto a + \frac{1}{z}$). $\endgroup$ Jun 29, 2012 at 15:53
  • 1
    $\begingroup$ Trivial examples: reciprocal, adding $17$. Non-trivial example: don't know any. $\endgroup$ Jun 29, 2012 at 15:55

1 Answer 1

29
$\begingroup$

This is the reverse of your question; you asked what happens to the value of a continued fraction whose terms are modified in a simple way, but you also implied that you were interested in what to do to the terms to effect simple operations on the value of the fraction.

There is an algorithm which, given a single continued fraction $x$, will give you back the continued fraction $ax+b\over cx+d$ for any fixed integers $a,b,c,d$.

There is an analogous algorithm which takes any two continued fractions $x$ and $y$ and yields the continued fraction for $axy+bx+cy+d\over exy+fx+gy+h$ for any fixed integers $a,\ldots, h$. By putting $\langle a,\ldots,h\rangle = \langle 1,0,0,0,0,0,0,1\rangle$, the algorithm calculates the continued fraction for $xy$; by putting $\langle a,\ldots,h\rangle = \langle 0,1,1,0,0,0,0,1\rangle$, the algorithm calculates the continued fraction for $x+y$.

These algorithms were first discovered in the 1970s by Bill Gosper. They are not too complicated, but they are not trivial either. To explain them in this forum would probably not be very productive.

Gosper's monograph is available here.

I have some slides for a talk on the subject that I gave at Haverford College a few years ago, and an implementation in C. I would not normally have chosen C for this work, but I wanted to make the point that the algorithm does not require the fancy features of language $X$ for any $X$.

I also recently corresponded with Art DuPre of Rutgers University, who, with Dave Reimer of the College of New Jersey recently discovered algorithms which take a continued fraction $x$ and calculates the continued fraction for $\frac12x$. I don't know that these are published yet, and I haven't looked at them closely.

Addendum: I took another look at the Dupre-Reimer algorithm. It is a mess. It is also unaccompanied by a proof, and I imagine that the easiest way to prove it would be to show that it synthesizes the same results as the Gosper algorithm, which seems simpler.

$\endgroup$
5
  • $\begingroup$ I suppose those algorithms are simpler than taking $<a,b,c,d,e,f,g,h>=<0,2,0,1,0,0,0,2>$ in Gosper's algorithm. $\endgroup$ Jun 29, 2012 at 20:10
  • $\begingroup$ I asked them that when they wrote to me, and they said that the algorithms were quite different from that. I planned to look at the algorithms carefully to make sure this was the case, but I haven't done it yet. Note that for $x+\frac12$ you can use the simpler single-input algorithm with only four parameters, and take $\langle a,b,c,d\rangle = \langle2,1,0,2\rangle$. $\endgroup$
    – MJD
    Jun 29, 2012 at 20:12
  • $\begingroup$ Yes, you have answered me to the reverse question, but thank you very much for this post, it's very useful, I accept it. $\endgroup$
    – Blex
    Jun 29, 2012 at 22:50
  • $\begingroup$ I take it from a quick glance at Gosper's monograph that these algorithms would work for an infinitely periodic continued fraction as well? For example, the continued fraction of $\sqrt{N}$ where $N$ is not a perfect square. $\endgroup$
    – user347489
    Aug 30, 2018 at 19:52
  • $\begingroup$ They work the same for finite, infinite periodic, and infinite non-periodic fractions. $\endgroup$
    – MJD
    Aug 30, 2018 at 20:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .