Generating bounds on $e^x$

Question

I had a question in which I had to find the value $\lfloor e^x \rfloor$. How can I generate bounds on $e^x$ so as to obtain its floor?

PS: I dont know how to use MathJax. I hope still the question is clear. Also $x$ here is greater than zero. I would prefer to obtain the result using series expansion of $e^x$.

Answer 1

You want to find $\lfloor e^x \rfloor$ using the series expansion for $e^x$. The short answer is that you need to calculate some number of terms of the expansion. The specific number of terms is a bit annoying, and depends very much both on the size of $x$ and on how near $e^x$ is to an integer.

Recall that

$$ e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \ldots $$

The following process will work to compute $\lfloor e^x \rfloor$ relatively quickly:

1. To get a bare minimum on the number of terms necessary, find out how many terms it takes to compute $e^x$ to within $1/2$. A basic overestimate on the error, coming from the Cauchy form of the remainder for the Taylor polynomial of $e^x$, is $$R_n < \frac{3^x}{(n+1)!} x^{n+1}$$ for an expansion including the degree $n$ term, so you need to calculate when $\frac{3^x}{(n+1)!}x^{n+1} < \frac{1}{2}$. I note that little is lost by overestimating $3^x$ by $3^{\lceil x \rceil}$. Call the resulting $n$ as $N_0$.

2. Compute the value of $e^x$ as estimated by the degree $n$ Taylor polynomial. I'll denote our approximation by $T_n$, so then $$ T_n = 1 + x + \cdots + \frac{x^n}{n!}.$$ As we can certainly assume $x$ is positive (as it's trivial to estimate the floor of $e^x$ for $x$ negative), the Taylor polynomial for $e^x$ is always an underestimate. If we are lucky and $T_n - \lfloor T_n \rfloor \in [0, 1 - R_{N_0})$, then you can stop, and $\lfloor e^x \rfloor = \lfloor T_n \rfloor$. Otherwise, we must continue.

3. Supposing that $T_{N_0} - \lfloor T_{N_0} \rfloor \in [1 - R_{N_0}, 1)$, we must now worry that the error from the approximation makes our estimate off by $1$. The simplest way to correct for this is to include additional terms from the Taylor expansion, until $T_N - \lfloor T_N \rfloor \in [0, 1 - R_N)$. If this terminates, then $\lfloor e^x \rfloor = \lfloor T_N \rfloor$.

   It is worth noting that by choosing cleverly, this algorithm will never actually terminate. For instance, by choosing $x = \ln 2$, so that $e^x = 2$, this algorithm will never terminate. This is always a danger when working with infinite series, and in practice one would choose a set precision and stick with it.

4. An interesting alternative last step would be to consider the boundary number $\lfloor T_N \rfloor + 1$. You could compute $\ln (\lfloor T_n \rfloor + 1)$ using whatever preferred method you have to whatever desired precision, and compare this value to $x$. If $x$ is smaller than the log estimate, then $\lfloor e^x \rfloor = \lfloor T_n \rfloor$. Otherwise, $\lfloor e^x \rfloor = \lfloor T_n \rfloor + 1$. And now the ambiguity problem from before is identifying whether or not $x = \ln 2$ (more generally, near $\ln m$ for some integer $m$), which is a long and hard problem in itself.