19
$\begingroup$

I have seen this question many times as an example of provoking creativity. I wonder how many ways there are to approximate $\sqrt{e}$ by hand as accurately as possible.

The obvious way I can think of is to use Taylor expansion.

Thanks

$\endgroup$
  • $\begingroup$ The nice thing about the Taylor expansion is that (i) it converges very quickly, and (ii) you can easily derive upper and lower bounds so you know how close you are to the right answer. $\endgroup$ – Rahul Apr 22 '14 at 16:16
  • $\begingroup$ Must it be a decimal approximation? $\endgroup$ – Brad Apr 22 '14 at 16:25
  • 1
    $\begingroup$ One consideration often neglected in these tasks: to a computer, decimal or binary division is usually an expensive operation, with integer multiplication a lot less expensive, and addition less expensive still. The accepted answer needs only five terms from the series to get within $10^{-9}$, but the fifth term alone involves $11!$ which is ten multiplications. The full computing complexity of that approach is more expensive than just counting five terms in the series, and ends up with a denominator that has 11 decimal digits. (continued) $\endgroup$ – alex.jordan Apr 24 '14 at 2:20
  • 2
    $\begingroup$ (resumed) Compare this to the continued fraction approach. If you calculated the convergent down to the $17$, you get an approximation of $\frac{34361}{20841}$, already within $10^{-9}$ of $e^{1/2}$ and the denominator is much smaller. To get to this point costs a total of 28 multiplications, all involving at most a two-digit number by at most a five-digit number. (And there are also 28 additions to get to this point, but those are less expensive than the multiplications.) My humble opinion: series are overrated but stay in people's hearts because they are prominent in calculus class. $\endgroup$ – alex.jordan Apr 24 '14 at 2:24
  • $\begingroup$ "but the fifth term alone involves 11! which is ten multiplications" And if you write a recursive subroutine for it, the cost of the storage of the program state word at every single call will dwarf all the arithmetic together. However, all it means is that not everything should be done in the most stupid way available ;) This is not to say that I do not admire continued fractions, on the contrary. So, for this particular case I voted for your approach, but if $1/2$ were $4/7$, say... $\endgroup$ – fedja Jun 15 '14 at 2:48

11 Answers 11

20
$\begingroup$

I found this series representation of $e$ on Wolfram Mathworld: $$ e=\left(\sum_{k=0}^\infty\frac{4k+3}{2^{2k+1}(2k+1)!}\right)^2. $$ Hence $$ \sqrt{e}=\sum_{k=0}^\infty\frac{4k+3}{2^{2k+1}(2k+1)!}. $$ Also from Maclaurin series for exponential function $$ e^{\large\frac{1}{2}}=\sum_{n=0}^\infty\frac{1}{2^n n!}. $$

$\endgroup$
  • 7
    $\begingroup$ Wow!? I have just found the middle series is extremely powerful! It only needs $5$ terms to yield accuracy $10^{-9}$!! $\endgroup$ – Tunk-Fey Apr 22 '14 at 16:43
  • 2
    $\begingroup$ @RandomVariable I've also realized your answer is the same as mine since the begining but I don't wanna claim this is only mine. Feel free for everyone to use it and +1 from me for your answer. :) $\endgroup$ – Tunk-Fey Apr 22 '14 at 18:41
  • 1
    $\begingroup$ Nice identity to start with @Tunk-Fey $\endgroup$ – Jeff Faraci Apr 23 '14 at 4:08
17
$\begingroup$

The rapidly-converging series representation of $\sqrt{e}$ in Tunk-Fey's answer can be derived from simply expressing the Maclaurin series of $e^{x}$ as the sum of its even terms plus the sum of its odd terms.

$$ \begin{align} e^{x}&= \sum_{n=0}^{\infty} \frac{x^{2n}}{(2n)!} + \sum_{n=0}^{\infty} \frac{x^{2n+1}}{(2n+1)!} = \sum_{n=0}^{\infty} \frac{x^{2n}(2n+1) + x^{2n+1}}{(2n+1)!} \\ &= \sum_{n=0}^{\infty} \frac{x^{2n}(2n+1+x)}{(2n+1)!} = \sum_{n=0}^{\infty} \frac{x^{2n}(4n+2+2x)}{2(2n+1)!} \end{align}$$

$\endgroup$
  • 2
    $\begingroup$ Very nice solution. $\endgroup$ – Jeff Faraci Apr 23 '14 at 4:07
12
$\begingroup$

If you apply the standard series expansion of $e^x$ to the case $x=-1/2$ and then find the reciprocal, it will converge faster than if you use $x=1/2$.

$\endgroup$
10
$\begingroup$

On a pocket calculator enter $2048$, ${1\over x}$, $+$, $1$, $=$, $x^2$ ($10$ times).

$\endgroup$
8
$\begingroup$

How accurately do you need it? One option is to use binomial expansion: $$ e^{\frac{1}{2}} \approx \Big(1+\frac{1}{n}\Big)^{\frac{n}{2}}=\sum_{k=0}^{\frac{n}{2}}\binom{\frac{n}{2}}{k}\frac{1}{n^k} $$ which you can make arbitrarily close to $e^{\frac{1}{2}}$ for various values of $n$.

$\endgroup$
  • $\begingroup$ Thanks Alex, I also thought of the limiting definition of $e$, I didn't know the binomial expansion. Good job, I think this is very doable by hand. I don't want to accept the right answer so soon. Let's see if someone else proposes other creative methods. $\endgroup$ – fast tooth Apr 22 '14 at 16:06
  • 7
    $\begingroup$ Even if you set $n = 1000$ you still only have four digits of accuracy. $(1+1/1000)^{500} = 1.6483...$, $\sqrt{e} = 1.6487...$ $\endgroup$ – Brad Apr 22 '14 at 16:10
  • 4
    $\begingroup$ this limit expression for $e$ converges very slowly. Very very slowly. $\endgroup$ – Ittay Weiss Apr 22 '14 at 16:23
  • $\begingroup$ @IttayWeiss With $n=1024=2^{10}$, we have $(1+(1/2)/2^{10})^{2^{10}}=1.64852008854402$ which has three exact digits. This requires only computing $1+1/2048$ (ten divisions by $2$ of $0.5$) and ten squarings. I's say it's pretty good if one has a simple calculator with the “square” key. $\endgroup$ – egreg Apr 22 '14 at 16:30
  • $\begingroup$ @egreg you have extraneous $1/2$ inside parentheses and too high power outside them. It should rather be $\left(1+2^{-10}\right)^{2^9}\approx 1.64831906$. $\endgroup$ – Ruslan Apr 22 '14 at 18:07
7
$\begingroup$

I would use the fact that $e \approx 2.7182818284$ and use Wikipedia on computing square roots. The digit by digit method will get you five decimals fairly quickly

$\endgroup$
  • 1
    $\begingroup$ +1 It should be totally fair game to have $e$ memorized to $2.718281828$. That initial pattern is too easy to remember. $\endgroup$ – alex.jordan Apr 24 '14 at 23:34
  • $\begingroup$ Plus computing square roots by hand is a lost art. Everyone should know how to do it. $\endgroup$ – Duncan Jun 17 '14 at 22:55
7
$\begingroup$

And here is another answer. There is a known continued fraction expansion for $e^{1/n}$. Continued fraction sequences converge quickly (although with so many 1s, this particular continued fraction converges on the slower end of things). The downside is that you can't use the $n$th convergent to quickly find the $n+1$st convergent, so you have to make a choice right away how deep to go. As @spin notes in the comments, you can refine your convergent using the previous two convergents and the next integer in the continued fraction expression.

$$e^{1/2}=1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{5+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{9+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{13+\cfrac{1}{1+\cfrac{1}{1+\cdots}}}}}}}}}}}}$$

$\endgroup$
7
$\begingroup$

As an alternative to series-based methods, there are differential equation based methods you can use.

If we recognize that $y=e^x$ is the solution to $y'=y$ with $y(0)=1$, and use Runge-Kutta with a small step size to approximate $y(1/2)$.

In this case, with just one step (using $h=1/2$ in the link), we obtain $e^{1/2}\approx1.6484375\ldots$, compared to the actual value of $e^{1/2}=1.64872127\ldots$.

With two steps, using $h=1/4$, we obtain $1.648699\ldots$.

With three steps, using $h=1/6$, we obtain $1.648716\ldots$.

With four steps, using $h=1/8$, we obtain $1.648716\ldots$.

With four steps, using $h=1/8$, we obtain $1.648719\ldots$.

In fairness, each "one" step in Runga-Kutta applied to this situation does require about seven multiplications. And since the step size needs to be decided from the start, you don't have the ability to refine your result further like you can with series by adding more terms. On the other hand a differential equation based method can give more accuracy in exchange for less computation in many cases.

$\endgroup$
6
$\begingroup$

Use the Power series to compute $x_n := \exp\left(-2^{-n}\right)$ for some $n \geqslant 1$ with high accuracy, and then compute

$$\sqrt{e} = \left(\frac{1}{x_n}\right)^{2^{n-1}}.$$

Using the negative exponent, and an exponent of smaller absolute gives you (much) faster convergence of the series, and the few operations of squaring and inverting don't lose much precision then. For e.g. $n = 3$, you get pretty good results for the first $10$ terms of the power series already.

$\endgroup$
2
$\begingroup$

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\root{\expo{}_{n}} = x_{n}}$. With Newton-Rapson: $\ds{x_{n + 1} = \half\pars{x_{n} + {e \over x_{n}}}\,,\quad x_{0} = 2}$

$\ds{\large\tt\mbox{With}\quad \color{#66f}{\Large n = 3}}$: \begin{align}&{\LARGE\sqrt{\expo{}}}\approx \frac{1}{2} \left\{\frac{1}{2} \left[\frac{1}{2} \left(2+\frac{e}{2}\right)+\frac{2 e}{2+\frac{e}{2}}\right]+\frac{2 e}{\frac{1}{2} \left(2+\frac{e}{2}\right)+\frac{2 e}{2+\frac{e}{2}}}\right\} = x_{3} \approx 1.648721295 \end{align}

$$ \mbox{Relative Error} = \verts{{x_{3} \over \root{\expo{}}} - 1}\times 100\ \% =1.48\times 10^{-6}\ \% $$

enter image description here

$\endgroup$
0
$\begingroup$

You can use the following identities:

  • $e=\lim_n(1+1/n)^n$,

  • $e=\lim_n\frac{n}{^n\sqrt{n!}}$,

Put a large value of $n$ and it should do. Of course you have to square-root the results.

$\endgroup$
  • $\begingroup$ hmm, then i have to find another method to take the square root by hand. $\endgroup$ – fast tooth Apr 22 '14 at 16:18
  • $\begingroup$ these converge quite slowly. $\endgroup$ – Ittay Weiss Apr 22 '14 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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