Iterative calculation of $e^x$

Question

Is there an iterative approximation method for calculating $e^x$, which only use basic operations (add, subtract, multiply, division), and which is capable of using an initial guess?

So, I have an initial guess for $e^x$, which is already a close value, and I'd like to have a formula, which I can apply, so the guess becomes better.

Something like we have for square root: $x_{i+1}=0.5\left(\frac{n}{x_i}+x_i\right)$. If I have an initial guess $x_1$, I can apply this formula to get better and better approximation for square root.

I derived this formula for $e^n$: $x_{i+1}=x_i\left(n+1-\ln(x_i)\right)$, but unfortunately I cannot use it, as it has $\ln()$, so it is slow to compute (it doesn't worth to use this iteration, as it is faster to compute $e^x$ directly).

Note: I'd use this, as I've written in my square root example: I have a guess, and I'd like to able to apply a formula, which gives a better approximation. So unfortunately Taylor series is not a solution for my problem (as far as I understand).

Note2: The main reason of this question is how to avoid calling the math library function exp(). So I need a solution which is faster than exp(). By faster I mean "faster on a current average PC". It could be possible, because I have a good approximation to begin with. Like one can normalize an almost unit length vector faster than calculating $1/\sqrt{\mathrm{length}}$, if we approximate $1/\sqrt{\mathrm{length}}$ around one. So, I have a good approximation to $e^x$, and I'd like to apply a simple, fast formula, which makes this approximation better.

Answer 1

You can use the Taylor Series for the Exponential Function

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

Answer 2

Update after your edit:

I reckon you have to compute values $e^x$ many times for nonnegative $x$-values in some large range. Then, following John Hughes'answer, I suggest the following: Prepare with as high precision as possible once and for all a table of the values $$a_n=e^{2^n}\qquad(n\geq0)\ .$$ The $a_n$ can be computed using the recursion $$a_0:=e,\qquad a_{n+1}:=\bigl(a_n\bigr)^2\quad(n\geq1)\ .$$ One has, e.g., $a_9\approx2.3\cdot10^{222}$.

The computation of $e^x$ for a given $x\geq0$ then proceeds as follows: Write $x$ in the form $$x=j+\xi,\qquad{\rm where}\quad j:=\lfloor x\rfloor,\quad\xi:=\{x\}\ .$$ Since $0\leq \xi<1$ you can easily compute $\eta:=e^\xi$ to high precision using the Taylor series. Concerning $j$, write $j$ in binary: $$j=\sum_{k=0}^m b_k2^k, \qquad b_k\in\{0,1\}\ .$$ Then (pick up the factors in increasing order!) $$e^x=\eta\>\prod_{b_k=1} a_k\ .$$ Original answer:

The exponential series can be morphed into the following recursive scheme: $$s_{-1}:=0,\quad s_0:=1,\qquad s_n:=s_{n-1}+{x\over n}(s_{n-1}-s_{n-2})\quad (n\geq1)\ .$$

Answer 3

As others have noted, you can use the Taylor series...but if you try to compute $e^{100}$ that way, you'll need a great many terms. Fortunately, you can instead compute $e^{50}$ and square the result. Or $e^{25}$ and square it twice. Or $e^{0.5}$, and raise it to the $200$ power. The advantage of this last one is that the numerator ($0.5^k$) gets small very fast, while the denominator gets large very fast, so you get very rapid convergence.

The disadvantage is that when you compute your result $r \approx e^{0.5}$, you find that $r^{200}\approx e^{100}$ contains an error that's substantially larger than the error in $r$, and you really need to do some calculus to decide what the optimal number of terms to use in computing $r$ might be.

Answer 4

You are almost there. Your proposed iteration using $\,\log\,$ only requires a fast way to calculate $\,\log.\,$ This is possible using the AGM method as explained in section $7.5.2$ of Elementary Functions: Algorithms and Implementation by Jean-Michel Muller or some other method you can choose. The AGM method gives a fast way of computing $\,F(x)\,$ the complete elliptic integral of the first kind. If $\, F(k^2) := \int_0^{\pi/2} dt/\sqrt{1 - k^2 \sin^2 t}, \,$ then the AGM can be used to compute it quickly. The function $\,F(k^2)\,$ has an approximation at $\,1^-\,$ given by $\, F(1 - (4/x)^2) \approx \log(x) + 4(\log(x)-1)/x^2. \,$ This method may not be ideal, but it can be used.

The same book in section $7.5.3$ Computing Exponentials with the AGM has iteration $(7.14)$ $\, x_{n+1} = x_n(1 + a - \ln(x_n)) \,$ for computing $\, \exp(a). \,$

Note that the AGM is used for fast methods to compute a number of elementary functions and $\pi.$ Of course, there are other methods, such as CORDIC. You can experiment with them. No matter how you compute logarithms, you can use that in your iteration for the exponential.