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'm trying to compute the values of differing degrees of continued fractions like $\sqrt 2$, e and other similar fractions. My theory was to take the reduced fraction at an arbitrary depth and the fraction that gets added in the next step and combine them somehow to compute the next deepest fraction.

So for example, $\sqrt 2$ can be expressed first as $\large\frac 1 2$ (the constant $1$ + I figured should be added on at the end) then as $\displaystyle \frac 1 {2 + \frac 1 2}$ which reduces to $\large\frac 2 5$. Then the next step $\displaystyle \frac 1 {2 + \frac 1 {2 + \frac 1 2}}$ which in turn reduces to $\large\frac 5 {12}$.

So in effect, what I'm trying to figure out is how I can go from $\large \frac 1 2$ (knowing the next step is $large\frac 1 2$) to $\large\frac 2 5$ and then from there again to $\large\frac 5 {12}$ - in a generic way that will work for other continued fractions.

Here's my original attempt ($\frac p q$ is the previously computed fraction, $\frac f g$ is the fraction to add in the next step) which doesn't work at all, but may help you see what I'm trying to do:

$$\frac {p_{n+1}} {q_{n+1}} = \frac {p_n\cdot g_{n+1}+f_{n+1}} {q_n\cdot g_{n+1}+g_{n+1}}$$

Anyways, I'm trying to compute continuous fractions to different depths, preferably inductively, given the previous step and the new fraction to add to the denominator. Any insight you can provide would be wonderful.

share|improve this question
1  
$\sqrt 2$ and other quadratic numbers have periodic continued fractions, and you can get the next best approximation from the pattern (simple ones like $\sqrt 2$ have a simple recurrence relation for numerators and denominators). In general, though, there is no such theory, because the partial continued fraction gives no information about the remaining difference. There is an algorithm for computing the continued fraction. Hardy and Wright "Theory of Numbers" has a good introduction to the theory. –  Mark Bennet Jun 24 '11 at 19:58
add comment

4 Answers 4

up vote 3 down vote accepted

If you are looking for a reccurence relation for convergents, for $[a_0;a_1;a_2;\ldots]$ it's $$ \frac{p_{n+1}}{q_{n+1}}=\frac{a_{n+1}p_n+p_{n-1}}{a_{n+1}q_n+q_{n-1}}. $$

P.S. For $\sqrt2=[1;2;2;2;\dots]$ it can be written in even nicer (first-order!) form: $$ \frac{p_{n+1}}{q_{n+1}}=\frac{p_n+2q_n}{p_n+q_n}. $$ Hence (for $\sqrt2$) $$ \begin{pmatrix}p_n\\q_n\end{pmatrix}=\begin{pmatrix}1&2\\1 &1\end{pmatrix}^n\begin{pmatrix}1\\0\end{pmatrix} $$ and it can be computed in $O(\log n)$ time.

(In fact, there is always a formula of this type for periodic continued fraction -- i.e. for quadratic irrationalities. If the period is $T$ it allows to compute $(p_{n+T},q_{n+T})$ knowing only $(p_n,q_n)$. Which, in turn, allows one to compute any convergent in logarithmic time.)

share|improve this answer
    
@Grigory M: I think you have a typo in $\dfrac{p_{n+1}}{q_{n+1}}=\dfrac{p_n+2q_n}{p_n+q_n}$. –  Américo Tavares Jun 25 '11 at 10:10
    
@Grigory: "1/1 -> 3/2 -> 7/5 -> 17/12 ->... " are fine but the coefficients should be the same in numerator and denominator. I would write $$\dfrac{p_{n+1}}{q_{n+1}}=\dfrac{2p_n+p_{n-1}}{2q_n+q_{n-1}}.$$ –  Américo Tavares Jun 25 '11 at 10:26
    
@Americo Both formulas are true. But yours is a second order recurrence relation, and I'm talking about a first order one (note that there is no "n-1" in that formula -- and that's not a typo!). –  Grigory M Jun 25 '11 at 10:29
    
@Grigory: OK. Thanks! –  Américo Tavares Jun 25 '11 at 10:40
1  
@Americo Well, this one was just $$\frac{p_{n+1}}{q_{n+1}}=1+\frac1{1+\frac{p_n}{q_n}}$$ — and it's not hard to see that the same trick works for any periodic continued fraction (cf. proof of quadratic irrationality of periodic continued fraction). Of all I said, the only difficult result is that any quadratic irrationality is periodic (at least, I don't understand it well enough to give a short proof). Anyway, standard reference is Davenport, Higher Arithmetic, I believe. –  Grigory M Jun 25 '11 at 12:43
show 3 more comments

I compute below

$$\displaystyle\begin{pmatrix}p_{n+1 } & p_{n } \\ q_{n+1 } & q_{n}\end{pmatrix}=\begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}^{n+1}.$$

Notation: Instead of $p_{n+1}$ and $q_{n+1}$ let me use respectivelly $A_n$ and $B_n$.

With the initial conditions $A_{-1}=1$, $B_{-1}=0$, $A_{0}=b_{0}$, $B_{0}=1$,

$$\displaystyle\begin{pmatrix}A_{\nu } & A_{\nu -1} \\ B_{\nu } & B_{\nu -1}\end{pmatrix}=\displaystyle\prod_{k=0}^{\nu }\begin{pmatrix}b_{k} & 1 \\ a_{k} & 0\end{pmatrix}\qquad(\text{with }a_0=1)\qquad(\ast)$$

is the matrix notation of the truncated generalized continued fraction

$$\dfrac{A_{n}}{B_{n}}=b_{0}+\underset{\nu =1}{\overset{n}{\mathbf{K}}}\left( \dfrac{a_{\nu}}{b_{\nu}}\right)=b_{0}+\dfrac{a_1}{b_1\ +}\ \dfrac{a_2}{b_2\ +\cdots}\ \ \dfrac{a_n}{b_n} \qquad (0)$$

(the first expression is the Gauss Notation ). Its fundamental second order recurrence relation is given by

$$\left\{ \begin{array}{c}b_{\nu }A_{\nu -1}+a_{\nu }A_{\nu -2}=A_{\nu } \\ b_{\nu }B_{\nu -1}+a_{\nu }B_{\nu -2}=B_{\nu }\end{array}\right. \qquad(\nu=1,2,\dots,n).\qquad (1)$$

For $a_k=1$, we have respectivelly

$$\displaystyle\begin{pmatrix}A_{\nu } & A_{\nu -1} \\ B_{\nu } & B_{\nu -1}\end{pmatrix}=\displaystyle\prod_{k=0}^{\nu }\begin{pmatrix}b_{k} & 1 \\ 1 & 0\end{pmatrix}\qquad(\text{with }a_0=1)\qquad(\ast\ast)$$

and

$$\dfrac{A_{n}}{B_{n}}=b_{0}+\underset{\nu =1}{\overset{n}{\mathbf{K}}}\left( \dfrac{1}{b_{\nu}}\right)\qquad (2)$$

From the equality

$$\sqrt{2}-1=\dfrac{1}{2+\sqrt{2}-1}=\dfrac{1}{2+\dfrac{1}{2+\sqrt{2}-1}}=\cdots $$

we get the following expansion for $\sqrt{2}$

$$\sqrt{2}=1+\underset{\nu =1}{\overset{\infty}{\mathbf{K}}}\left( \dfrac{1}{2}\right) =1+\dfrac{1}{2\ +}\ \dfrac{1}{2\ +}\ \ \dfrac{1}{2\ +\cdots}\qquad (3)$$

whose convergents $A_n$ and $B_n$ are such that

$$\dfrac{A_{n}}{B_{n}}=1+\underset{\nu =1}{\overset{n}{\mathbf{K}}}\left( \dfrac{1}{2}\right)\qquad (4)$$

Since $a_k=1,b_k=2 (k\ge 1)$, the fundamental recurrence for $\sqrt{2}$ is given by the following system

$$\left\{ \begin{array}{c}2A_{\nu -1}+A_{\nu -2}=A_{\nu } \\ 2B_{\nu -1}+B_{\nu -2}=B_{\nu }\end{array}\right. \qquad(\nu=1,2,\dots,n).\qquad (5)$$

or this product of matrices

$$\displaystyle\begin{pmatrix}A_{\nu } & A_{\nu -1} \\ B_{\nu } & B_{\nu -1}\end{pmatrix}=\displaystyle\prod_{k=0}^{\nu }\begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}=\begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}^{\nu}\qquad(\nu=1,2,\dots,n)\qquad(\ast\ast\ast)$$

or in your notation, for $n=0,1,2,\dots$

$$\displaystyle\begin{pmatrix}p_{n+1 } & p_{n } \\ q_{n+1 } & q_{n}\end{pmatrix}=\begin{pmatrix}2 & 1 \\ 1 & 0\end{pmatrix}^{n+1}$$

This is the most compact form I am aware of. Hope this helps!


Generalization: For $\sqrt{1+x}$ one can use the algebraic identity

$$\sqrt{1+x}-1=\dfrac{x}{2+\sqrt{1+x}-1}=\dfrac{x}{2+\dfrac{x}{2+\sqrt{1+x}-1}}=\cdots $$


References

  • Oskar Perron, Die Lehre von den Kettenbrüchen, 3.ª ed., vol. II, B. G. Teubner, Stuttgart, 1957.

  • Lisa Lorentzen and Haakon Waadeland, Continued Fractions and Applications, North-Holland, Amsterdam, 1992.

  • Sergey Khrushchev , Orthogonal Polynomials and Continued Fractions: From Euler's Point of View, Cambridge University Press, 2008.

share|improve this answer
    
That is far more math than I can possibly ever hope to understand :P but +1 for the effort, I hope other people smarter than me will be able to appreciate it. –  dimo414 Jun 25 '11 at 23:37
add comment

An alternative method for generating the convergents of continued fraction, which is essentially a stabilized version of the recurrence in Américo's answer, is due to Lentz, Thompson and Barnett.

Given a continued fraction

$$b_0+\cfrac{a_1}{b_1+\cfrac{a_2}{b_2+\cdots}}$$

the Lentz-Thompson-Barnett scheme relies on the two ratios $C_n=A_n/A_{n-1}$ and $D_n=B_{n-1}/B_n$, where $A_n$ and $B_n$ are the nth numerators and denominators (using the same notation in Américo's answer).

Using the recursions given in Américo's answer, the recursions for $C_n$ and $D_n$ are quickly determined to be

$$C_n=b_n+\frac{a_n}{C_{n-1}},\qquad D_n=\frac1{b_n+a_n D_{n-1}}$$

Letting $Y_n=\frac{A_n}{B_n}$ be the $n$-th convergent, Lentz-Thompson-Barnett runs like so:

$\displaystyle Y_0=b_0,\,C_0=Y_0,\,D_0=0$
$\text{for }n=1,2,\dots$
$$D_n=\frac1{b_n+a_n D_{n-1}}$$ $$C_n=b_n+\frac{a_n}{C_{n-1}}$$ $$H_n=C_n D_n$$ $$Y_n=H_n Y_{n-1}$$ $\text{end for}$

Some modifications are needed in cases where certain denominators become zero, but I'll skip mentioning those since they don't seem to occur for continued fractions of surds.

P.S. Of course, if $b_0=0$, start with $b_1$ instead of $b_0$ and the required fractions become $a_1/Y_n$... ;)

share|improve this answer
add comment

Someone posted an answer here about two hours ago that was correct, but they seem to have deleted it, or SE is glitching and I can't see it. I'll gladly give you the Accepted Answer if you come back and post it again.

If they don't, I was able to find effectively the same answer on Wikipedia, of course. I should have done a little more digging, but if anyone's in the same boat as me, here's the answer, enjoy.

Equation for successive convergents from Wikipedia

share|improve this answer
add comment

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.