Approximating Euler’s Constant From Scratch

Posted on March 17, 2008
Filed Under Math, Programming |

Or: Calculus You Will Use Either Every Day or Never

Approximating Constants

We will be calculating Euler’s constant, e, by starting off close to the correct value, and then moving closer and closer until we get to the correct value. This is known as approximation.

There are a few different ways to do this. A few are listed below:

  1. Find a function that evaluates to e and approximate the function.
  2. Rephrase the problem as a root-finding problem and find solutions via famous root-finding methods (any of Householder’s Methods, Bisection, the Secant Method, etc).
  3. Rephrase the problem as a fixed-point problem (I.E., find an \alpha such that f(\alpha)=\alpha.

I have opted to write about number 1., find an approximating function using Taylor Series. Why did I pick it? The math is easy, and helps teach basics of approximation. Taylor approximation is generally slow, and is often better used to approximate functions over intervals rather than particular constants. This is just a particular application of Taylor series.

If you have not taken a Calculus course, the material presented here may or may not be lost on you.

Taylor Series

Assume that f(x) is continuous and infinitely differentiable. If we want to know values of f(x) near \alpha, we can use the formula below to determine just how many decimal places we need to use in our approximation.

Formula for a Taylor Series with infinite terms:

If $f(x)$ is infinitely differentiable and continuous, a Taylor Series of $f(x)$ about \alpha is written:

$f(x) = \sum_{k=0}^{\infty}\frac{(x-\alpha)^k}{k!}f^{(k)}(\alpha)$

This may look a little confusing, but once you start trying a few test functions, it gets really easy to start approximating the function.

Example: $f(x) = e^x$ about \alpha

The zeroth term:

$f^{(0)}(\alpha)\frac{(x-\alpha)^0}{0!} = f(\alpha) = e^\alpha$[/tex]

The first term:

$f^{(1)}(\alpha)\frac{(x-\alpha)^1}{1!} = (x-\alpha)f\prime(\alpha) = (x-\alpha)*e^\alpha$

The result:

$f(x) = e^\alpha + (x-\alpha)e^\alpha + \frac{(x-\alpha)^2}{2!}e^\alpha + \frac{(x-\alpha)^3}{3!}e^\alpha + \ldots$

Error in Taylor Series

If we add up infinitely many terms, we will have an infinite degree polynomial that exactly represents the function. However, I can’t wait for my computer to calculate infinite terms, so we need to know when to stop.

Remainder of a Taylor Polynomial

In general, the error for an nth degree Taylor Polynomial of a function $f(x)$ about \alpha can, for some $\varepsilon_x, x \leq \varepsilon_x \leq \alpha$ be written as follows:

$R_n(x) = \frac{(x-\alpha)^{n+1}}{(n+1)!}f^{(n+1)}(\varepsilon_x)$

When we are calculating how many terms we need, we need, in part, to find the maximum value of $f^{(n+1)}(\varepsilon_x)$ over the area $[x, \alpha]$.

Actually Calculating e

We want to (for some twisted reason) compute e using a Taylor series without the calculation being in terms of e. One way to do this is to calculate the Taylor series for $e^x$

Taylor Series for e^x about \alpha:

$e^x = 1 + (x-\alpha) + \frac{1}{2!}(x-\alpha)^2 + \frac{1}{3!}(x-\alpha)^3 + \ldots

We should also note that $e^1=e$, so we can go on ahead and substitute 1 for x:

Taylor Series for e^1 about \alpha:

$f(x) = e^\alpha +e^\alpha(1-\alpha) + e^\alpha\frac{1}{2!}(1-\alpha)^2 + \ldots

Set \alpha equal to zero. Magically, all of the es will disappear, and we will be able to evaluate e without having to use e.

Taylor Series for e^1 about 0:

$f(x) = 2 + 1/2! + 1/3! + \ldots$

What Degree Polynomial do we Use?

We can play around with our error formula until we determine how many steps will be needed.

Simplifying Error Formula

$error = f^{(n+1)}(\varepsilon_x)\frac{(x-\alpha)^{(n+1)}}{(n+1)!}$

$error = f^{(n+1)}(\varepsilon_x)\frac{(1-\alpha)^{n+1}}{(n+1)!}$

$error = f^{(n+1)}(\varepsilon_x)\frac{(1)^{n+1}}{(n+1)!}$

$error = e^{\varepsilon_x}\frac{1}{(n+1)!}$

We see that we need to determine an upper bound on the value of e^{\varepsilon_x} between 0 and 1. An easy upper bound for us is 2.72, as we know that it is larger than e.

Final error formula

The error in our Taylor Series f(x) = e^x, f(1) about 0 is:

$error = 2.72/(n+1)!$

Naieve C++ Implementation

Please note that this code is susceptible to a few calculation errors, including mismatched-precision addition.

double calc_e(int degree)
{
    double answer = 0;
    double current_factorial = 1;
    for(int i=0; i<degree;>
    {
        answer+=1./current_factorial;
        current_factorial*=(i+1);
    }
    return answer;
}</degree;>

Output for various Taylor polynomials:

Taylor poly of degree 1:2
Taylor poly of degree 2:2.5
Taylor poly of degree 3:2.66666667
Taylor poly of degree 4:2.70833333
Taylor poly of degree 5:2.71666667
Taylor poly of degree 6:2.71805556
Taylor poly of degree 7:2.71825397
Taylor poly of degree 8:2.71827877
Taylor poly of degree 9:2.71828153
Taylor poly of degree 10:2.7182818
Taylor poly of degree 11:2.71828183

This gives us precision of less than $10^8$ with 11 steps. Checking the error formula, we see that 2.71/12! is less than $10^8$, but 2.71/11! is greater than $10^8$, so our error is also correct.

Popularity: 18% [?]

Comments

Leave a Reply