2
$\begingroup$

I'm coding a program to calculate the value of $e^x$ by using the Taylor expansion, that is:

$$ e^x =\sum_{k=0}^\infty \frac{x^k}{k!} $$

from math import factorial
def e_x(x, n):
    return sum(pow(x, k)/factorial(k) for k in range(n))

Edit: Python seems to handle large integers pretty well so I'm more interested in the algorithm itself.

I want to avoid overflows during the calculation of the $k!$, so my intuition is that by looking at the $k$th-term and trying to do intermediary divisions an overflow might be avoided.

My naive solution was to just do $\frac{x}{k} \cdot \frac{x}{k-1} \cdot \ldots \cdot \frac{x}{1} \cdot \frac{x}{1}$, but the error became unbearable after some few iterations. I'm not using any high (arbitrary) accuracy floating point library (although I'm interested in knowing how would this be implemented in those).

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 26 '17 at 17:52
  • 2
    $\begingroup$ Are you interested in calculating $e^x$ accurately by any method or specifically using Taylor series ? Are you using a high (arbitrary) accuracy floating point library or limited to a specific accuracy of representation ? These are major issues. $\endgroup$ – StephenG Apr 26 '17 at 21:04
  • $\begingroup$ Edited, maybe it's clearer now. $\endgroup$ – Aristu Apr 26 '17 at 22:25
4
$\begingroup$

Of course there are better numerical ways to compute exponential, but if you want to use Taylor expansion only, the better approach is to reformulate the expansion to avoid computing large nominators and denominators. This leads to an $O(n)$ algorithm, where $n$ is the number of iterations. Yours is $O(n^2)$ if you compute factorial and power literally (probably the python library is computing factorial with a gamma function and power with exp).

Here is a javascript program. print() is a function to write strings to console.

function myexp(x, max_itr)
{
    var y = 1.0, t = 1.0;
    for (var i = 1; i < max_itr; ++i) {
        t *= x / i;
        y += t;
    }
    return y;
}

var x = 1.2;
print("Math.exp: " + Math.exp(x));
print("10 iterations: " + myexp(x, 10));
print("99 iterations: " + myexp(x, 99));

The output is:

Math.exp: 3.3201169227365472
10 iterations: 3.3201150098285708
99 iterations: 3.3201169227365472

EDIT:

Alternatively, you can reformulate Taylor expansion as:

$$ e^x = 1 + \frac{x}{1}\left(1+\frac{x}{2}\left(1+\frac{x}{3}\left(1+\cdots\right)\right)\right)$$

An implementation in javascript:

function myexp2(x, max_itr)
{
    var y = 0.0;
    for (var i = max_itr; i >= 1; --i)
        y = 1.0 + x / i * y;
    return y;
}
$\endgroup$
  • 2
    $\begingroup$ It might be worth pointing out to the OP that the alternative formulation is similar to the Horner's rule for the evaluation of a polynomial. $\endgroup$ – Massimo Ortolano Apr 27 '17 at 19:44
  • 2
    $\begingroup$ Yes, it is inspired by Horner's rule. I didn't mention it because I forgot its name. Thanks for the info! $\endgroup$ – user172818 Apr 28 '17 at 1:28

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.