Could $\sum e^{a_i}$ be simplified? Does it have an identity?

Question

$\sum_{i=1}^n e^{a_i}$ (where $a_i \in \mathbb R$) is expensive for large $n$ (a sum and $n$ exponential operations). I was wondering if there is any way for simplifying this?

Answer 1

One possible way to reduce the cost of the exponentiation operation may be to replace exponentiation involving large exponents with multiplications. This is what I mean:

Assume that $\{a_i\}$ is sorted in ascending order (if not, sort them first), so that $a_{i+1}\geq a_i$. Now, let's use the notation $$ A(n) = \sum_{i=1}^n e^{a_i} $$ Obviously, $A(1)=e^{a_1}$. Now, we can write $$ A(2)=A(1)+e^{a_2} $$ But we could also write this as $$ A(2) = A(1)+b_1e^{a_2-a_1} $$ where $b_1=e^{a_1}$. Similarly, we have $$ A(3)=A(2)+b_2e^{a_3-a_2} $$ where $b_2=e^{a_2}=b_1e^{a_2-a_1}$. If we define the sequence $$ b_{i+1} = e^{a_{i+1}-a_i}b_i $$ with $b_1=e^{a_1}$, then we can write $$ A(n+1)=A(n)+b_{n+1} $$ The advantage of this is that, while $a_n$ may be very large, and thus require a lot of computation, it may be much quicker to calculate the various $b_i$. It requires just as many exponentiation operations, but reduces the size of the exponent significantly, which may save on operation cost.

However, it is subject to the exponentiation cost relationship. If the cost of exponentiation remains almost constant with size of the exponent, then this will actually be slower than simply evaluating the exponentials directly, due to the added multiplications.