2
$\begingroup$

I know that famous numbers like $\pi$ and $e$ have multiple representations as continued fractions and I'm fascinated with the variety of representations.

My question: What continued fraction for $e$ is most computationally efficient? A proof or a link to one for why a method is optimal would be of great interest to me.

Here, my metric for "computational efficiency" is achieving the most precise decimal places with a fixed number of terms generated in the continued fraction.

$\endgroup$
5
  • $\begingroup$ when you say a given number of terms what do you mean? Decimal places? $\endgroup$
    – Asinomás
    Dec 11, 2015 at 0:26
  • $\begingroup$ Do you want to minimize $\frac{|e-a/b|}{b}$, where $\frac{a}{b}$ is the continued fraction approximation? $\endgroup$
    – Asinomás
    Dec 11, 2015 at 0:27
  • 2
    $\begingroup$ Correct me if I'm wrong, but I believe the simple continued fraction for $ e $ is unique and that the convergents are optimal rational approximations to $ e $ (in the sense that you can't find a better approximation with a smaller denominator). $\endgroup$
    – littleO
    Dec 11, 2015 at 0:32
  • $\begingroup$ @littleO Is there a proof somewhere with that result? $\endgroup$
    – Xoque55
    Dec 13, 2015 at 17:54
  • $\begingroup$ @littleO, optimal approximation with the same size of denominator. Any continued fraction that gives bigger denominators for the same number of steps might be an improvement $\endgroup$
    – Yuriy S
    Feb 18, 2016 at 15:56

2 Answers 2

Reset to default
4
$\begingroup$

You would think that the simple continued fraction for $e$ is the best, but actually it's not.

Simple continued fraction for $e$ is:

$$e_n=[2;1,2,1,1,4,1,1,6,1,1,8,\dots]$$

Without counting the integer term we have:

$$e_5=\frac{87}{32}=e+0.00047\dots$$

$$e_8=\frac{1264}{465}=e-2.3 \cdot 10^{-6}$$

However, if we take the continued fraction for $\frac{e-1}{2}$, we get much better results:

$$e_n=1+2[0;1,6,10,14,18,22,26,\dots]$$

Not counting integer term (again) we have:

$$e_5=\frac{49171}{18089}=e+2.3 \cdot 10^{-10}$$

$$e_8=\frac{848456353}{312129649}=e-6.0 \cdot 10^{-19}$$

As you can see, it converges radically faster. And it also has an easier pattern - just start with $6$ and add $4$ at each step.

There are a lot of other interesting continued fraction which allow you to compute $e$. For example:

$$\tanh(1)=[0;1,3,5,7,9,11,13,15,17,19,21,\dots]$$

$$\tanh(1)=\frac{2}{1+e^{-2}}-1$$

$\endgroup$
1
  • $\begingroup$ Superb examples! Thanks for reviving this. Is there a way to construct even faster continued fractions or prove that this one is fastest? $\endgroup$
    – Xoque55
    Feb 19, 2016 at 3:36
3
$\begingroup$

If you allow generalized continued fractions $$ b_0 + \dfrac{a_1}{b_1 + \dfrac{a_2}{b_2 + \ldots}}$$ for positive integers $a_i$ and $b_i$, there is no "optimal" answer for the given criterion.
You can achieve arbitrary accuracy in any given number of terms, at the expense of having large numbers $a_i$ and $b_i$. Namely, let $r_1, r_2, \ldots$ be any sequence of positive rationals converging to $e$ with $r_i$ decreasing for even $i$ and increasing from odd $i$. We take $b_0 = 0$, $r_1 = a_1/b_1$, $a_2$ and $b_2$ so $$b_1 + \dfrac{a_2}{b_2} = \dfrac{a_1}{r_2} $$ which makes $$ r_2 = \dfrac{a_1}{b_1 + \dfrac{a_2}{b_2}}$$ $a_3$ and $b_3$ so $$ b_2 + \dfrac{a_3}{b_3} = \dfrac{a_2}{\dfrac{a_1}{r_3} - b_1} $$ which makes $$r_3 = \dfrac{a_1}{b_1 + \dfrac{a_2}{b_2 + \dfrac{a_3}{b_3}}}$$ etc.

$\endgroup$

You must log in to answer this question.

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