# How to find continued fraction of pi

I have always been amazed by the continued fractions for $\pi$. For example some continued fractions for pi are:

$\pi=[3:7,15,1,292,.....]$ and many others given here.

Similarly some nice continued fractions for $e$ and it's derivatives are given here.I have tried to prove that the are indeed the continued fractions but did not get very far.If any one can can help it would be great(especially if there is some easy way to get continued fraction of derivatives of e from the original continued fraction of e).Here derivatives of e I mean $\sqrt e,\frac{e-1}{e+1}$ etc.

-
None of the answers so far explain how to get the generalized continued fraction expansions for $\pi$, which are exact formula. –  Grumpy Parsnip Mar 18 '14 at 17:30

Recently I have had some misgivings about using the other listed methods to compute continued fractions. It seems very inconvenient to be required to have a very good decimal approximation of your number before computing the convergents you want.

Here is a paper by Shiu which gives an algorithm for computing continued fractions without needing to know more decimal digits at each stage; it only requires your number ($\pi$ in your case) to be a zero of a sufficiently nice differentiable function. Here is the abstract:

An algorithm for the computation of the continued fraction expansions of numbers which are zeros of differentiable functions is given. The method is direct in the sense that it requires function evaluations at appropriate steps, rather than the value of the number as input in order to deliver the expansion. Statistical data on the first 10000 partial quotients for various real numbers are also given.

As for proving that a number has a specified continued fraction, that is much harder. For instance, there is no known pattern for the convergents of $\pi$ (and if you could find one, it would be pretty monumental). $e$ is special because its continued fraction follows a known pattern, which can be proved using so called Padé approximants. See one proof here.

-
Thank you i was actually looking for an answer like this –  happymath Mar 23 '14 at 10:31

Here is how you find the continued fraction for any number at all. Say the number is $x_0$.

First, let $a_0$ be the largest integer that does not exceed $x_0$. That is, $a_0 = \lfloor x_0\rfloor$. And let $b_0$ be the fractional part of $x_0$, that is $b_0 = x_0 - a_0$. In our example, \begin{align}x_0&=\pi,\\ a_0 &= 3,\\ b_0 &= 0.14159\ldots.\end{align}

Now we write \begin{align}x_0 & = a_0 + b_0 \\ & = a_0 + \frac{1}{x_1}\end{align} where $x_1 = \frac1{b_0}$. In this case we have $x_1 = \frac{1}{0.14159\ldots} = 7.0625\ldots$.

Then repeat: let $a_1 = \lfloor x_1\rfloor, b_1 = x_1-a_1,$ and $x_2 = \frac1{b_1}$. In this case we have $a_1 = 7, b_1 \approx 0.0625\ldots$, and $x_2 = 15.996\ldots$. At this point have $$\pi = 3 + \cfrac{1}{7+\cfrac{1}{15.996\ldots}},$$ and in general $$x_0 = a_0 + \cfrac{1}{a_1+\cfrac{1}{x_2}}$$

Repeat again: let $a_2 = \lfloor x_2\rfloor, b_2 = x_2-a_2,$ and $x_3 = \frac1{b_2}$. In this case we have $a_2 = 15, b_1 \approx 0.996\ldots$, and $x_3 = 1.003\ldots$.

Repeat as desired, or stop if $x_i$ becomes 0, which will happen if and only if the original $x_0$ was rational.

The $a_i$ are the terms of the continued fraction expansion.

For expressions like $$\frac{e-1}{e+1}$$ there is an algorithm you can use, due to Bill Gosper, which takes the continued fraction for $e$ as input and emits the terms of $\frac{e-1}{e+1}$ as output. The algorithm is too long to describe in detail here, but you can read it in Gosper's original monograph or a shorter explanation here. The algorithm will actually calculate $$\frac{ax+b}{cx+d}$$ for any integer $a,b,c,d$ and continued fraction $x$; for $\frac{e-1}{e+1}$ you need to take $a=c=d=1, b=-1,$ and $x=e$.

Note that this does not require a decimal approximation for $e$; all it requires is the continued fraction for $e$, which is simple: $[2; 1,2,1,1,4,1,1,6,1,1,8,1\ldots]$. The Gosper monograph also gives an algorithm for extracting a continued fraction for $\sqrt x$ when the continued fraction for $x$ is known.

You asked how to know, when calculating a continued fraction for $\pi$, how much precision you need in the input decimal. Suppose you have calculated that $\pi \approx [p_0; p_1, p_2, \ldots p_n]$. Then you know that $$[p_0; p_1, p_2, \ldots p_n]\lt \pi \lt [p_0; p_1, p_2,\ldots, p_{n-1}]$$ if $n$ is even, or with the inequalities reversed if $n$ is odd. Now the $[p_0; \ldots]$ parts are rational numbers, so you can look at the denominators and see if your approximation to $\pi$ was good enough to justify continued fractions of that precision.

You also asked how, if you don't already have a decimal expansion for $\pi$, you can calculate the continued fraction. The answer is, you calculate it the same way that you calculate the decimal expansion for $\pi$ in the first place: by using the terms of an infinite series. For example, you might use the well-known series $$\sum_{k=0}^\infty\frac{2^{k+1} k!^2}{(2k+1)!}=\pi.$$ Each term of this series is a single rational number. You can start with $x=0$ and use the Gosper algorithm to accumulate the terms into $x$, extracting a term of output when possible, because $x' = x+\frac pq = \frac{qx+p}{0x+q}$ which has the required form. Whenever the integer part of $x$ and $x'$ is the same, that is the next term of the continued fraction for $\pi$; otherwise, set $x←x', x'←x'+\frac pq$ where $\frac pq$ is the next rational number in the series, and continue. (Disclaimer: I have not actually tried this, but it might work.)

-
Hm, but how do you actually carry out that computation? You'd first have to compute enough digits of $\pi$ - but how do you know how many you'll need to compute $n$ terms of the continued fraction expansion? –  fgp Mar 18 '14 at 16:54
$\pi$ is a bit of an odd case, because the continued fraction expansion of $\pi$ is not understood at all. The calculation of the continued fraction for $\frac{e-1}{e+1}$ is much easier, because its input is the continued fraction for $e$, which is quite regular. ($e = [2; 1,2,1,1,4,1,1,6,1,\ldots]$) But for $\pi$ there is no such simple answer. –  MJD Mar 18 '14 at 16:57
@fgp There probably isn't an easy answer to that. Since these numbers are irrational, the truncation can be fairly unpredictable. I would recommend "start with a lot of significant figures, keep track of how many you have, and if you run out before you reach $n$, start over with twice as many". –  DanielV Mar 18 '14 at 17:00
@MJD can we do such only for $\frac{ax+b}{cx+d}$ what about $x^2$ and others are there methods to solve for them –  happymath Mar 18 '14 at 17:03
@DanielV Yeah, that's the brute-force approach. The question is - do you have to start over? The existing coefficients won't change, so maybe you can fudge the "remainder" (for the lack of a better word) after computing more digits. More generally - say you have a series expansion of some $v = \sum_{i=0}^\infty v_i$, $v_i \in \mathbb{Q}$, and know some (computable) bound $B(n) \geq |\sum_{i=n+1}^\infty v_i|$. Can you compute the continued fraction expansion of $v$ from that with bounded memory, not counting the memory used to store the output coefficients? –  fgp Mar 18 '14 at 17:06

The digits in a continued fraction are given by

$$a_0 = x$$ $$a_n = (a_{n-1} - \lfloor a_{n - 1}\rfloor)^{-1}$$

$$d_n = \lfloor a_n \rfloor$$

Continued fraction for $\pi$:

$$\begin{array} {c|c c|c} n & & a_n & d_n \\ \hline 0 & & 3.1416 & 3 \\ \hline 1 & 0.1416^{-1} & = 7.0625 & 7 \\ \hline 2 & 0.0625^{-1} & = 15.9966 & 15 \\ \hline 3 & 0.9966^{-1} & = 1.0034 & 1 \\ \hline 4 & 0.0034^{-1} & = 292.6346 & 292 \\ \hline 5 & 0.6346^{-1} & = 1.5758 & 1 \\ \hline \end{array}$$

Continued fraction for $e$:

$$\begin{array} {c|c c|c} n & & a_n & d_n \\ \hline 0 & & 2.7183 & 2 \\ \hline 1 & 0.7183^{-1} & = 1.3922 & 1 \\ \hline 2 & 0.3922^{-1} & = 2.5496 & 2 \\ \hline 3 & 0.5496^{-1} & = 1.8194 & 1 \\ \hline 4 & 0.8194^{-1} & = 1.2205 & 1 \\ \hline 5 & 0.2205^{-1} & = 4.5356 & 4 \\ \hline \end{array}$$

Continued fraction for $\sqrt{e}$: $$\begin{array} {c|c c|c} n & & a_n & d_n \\ \hline 0 & & 1.6487 & 1 \\ \hline 1 & 0.6487^{-1} & = 1.5415 & 1 \\ \hline 2 & 0.5415^{-1} & = 1.8467 & 1 \\ \hline 3 & 0.8467^{-1} & = 1.1810 & 1 \\ \hline 4 & 0.1810^{-1} & = 5.5250 & 5 \\ \hline 5 & 0.5250^{-1} & = 1.9049 & 1 \\ \hline \end{array}$$

Continued fraction for $\frac {e - 1} {e + 1}$:

$$\begin{array} {c|c c|c} n & & a_n & d_n \\ \hline 0 & & 0.4621 & 0 \\ \hline 1 & 0.4621^{-1} & = 2.1640 & 2 \\ \hline 2 & 0.1640^{-1} & = 6.0993 & 6 \\ \hline 3 & 0.0993^{-1} & = 10.0711 & 10 \\ \hline 4 & 0.0711^{-1} & = 14.0554 & 14 \\ \hline 5 & 0.0554^{-1} & = 18.0454 & 18 \\ \hline \end{array}$$

It's more of a computation than a proof. Just make sure you have enough digits. When you start looking at the continued fractions that are patterns, then establishing the pattern actually requires proof techniques instead of just arithmetic.

-
my actual problem is i do not know the exact values so may be i can go till some digits but afterwards i have no proof that the digits are right i would actually like to establish the pattern but i do not know how to do that –  happymath Mar 18 '14 at 16:50
That's a numerical analysis problem....I suggest you look up "significant figures". –  DanielV Mar 18 '14 at 16:53
i am sorry may be I am not clear, I would like to establish the pattern with some proof rather than just do an approximate analysis –  happymath Mar 18 '14 at 16:55
@happymath What you are asking for in your last comment is not known for $\pi$. See the last paragraph of my answer. –  Daenerys Naharis Mar 20 '14 at 17:40