Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}}}} $$

share|improve this question
4  
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}$). –  Qiaochu Yuan Jun 29 '12 at 15:53
    
Trivial examples: reciprocal, adding $17$. Non-trivial example: don't know any. –  André Nicolas Jun 29 '12 at 15:55

1 Answer 1

up vote 7 down vote accepted

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 cd+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.

share|improve this answer
    
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. –  Robert Israel Jun 29 '12 at 20:10
    
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$. –  MJD Jun 29 '12 at 20:12
    
Yes, you have answered me to the reverse question, but thank you very much for this post, it's very useful, I accept it. –  Blex Jun 29 '12 at 22:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.