# How to Efficiently Compute a Sum of Exponentials?

In embedded code I want to efficiently compute:

$\sum_{k=1}^{N}y_k \cdot e^{a\cdot k}$,

$\sum_{k=1}^{N}y_k\cdot k \cdot e^{a\cdot k}$ and

$\sum_{k=1}^{N}y_k\cdot k^2 \cdot e^{a\cdot k}$.

Here $a$ is a scalar and $y_k$ is the k-th value in an array with $N$ elements.

These sums needs to be computed for many values of $a$.

Given that the array $y$ remains constant, is there an efficient way to do this without having to recompute the full sum of exponentials for every new value $a$?

• you can find your second and third sum by an simple (numeric) derivative w.r.t. $a$ – tired Jan 2 '18 at 14:49
• One observation to make is that, while you've written it as a sum of exponentials, you can just as easily let $x=e^a$. In that case the first sum is just the polynomial $y(x)=\sum_{k=1}^N y_k x^k$; the others rest can be written as $x\frac{d}{dx}y(x)$ and $x\frac{d}{dx}\left(x\frac{d}{dx}y(x)\right)$ respectively. So this amounts to computing $y(x)$, $y'(x)$, $y''(x)$. (This is basically the same idea as @tired suggests, though theirs is actually more efficient.) – Semiclassical Jan 2 '18 at 14:51
• Thank you for the insight. I'm not sure if I understand you correctly. To me it seems that computing the first and second derivative is equally expensive as computing the other 2 sums. – Luc Jan 2 '18 at 16:07

One may see the sum $$\sum_{k=1}^{N}y_k \cdot e^{a\cdot k}$$ as a polynomial function $$P_N(x)=\sum_{k=1}^{N}y_k \cdot x^{k}$$ valued at $x=e^a$.
One may exploit the Taylor formula $$P_N(x) = \sum \limits_{k=0}^N \dfrac{P_N^{(k)}(\alpha)(x-\alpha)^k}{k!}, \tag {*}$$ by storing all $P_N^{(k)}(\alpha)$ in a memory only once and use the above identity to get a value of $P_N$ at any $x$.
• Thank you for your answer. I am not sure if I understand you correctly. Is this cheaper than computing the sum of exponentials? It seems that for each new value of $a$ this would still require me to evaluate a sum with N terms in which each term $k$ requires $k$ multiplications. I do not konw the values of $a$ in advance. – Luc Jan 2 '18 at 15:47
• One may use Horner's method (which requires only $n$ additions and $n$ multiplications) to evaluate $P_N(x)$. Even with this method, the computation above does not seem an optimal solution. My answer above aims at showing that, since the polynomial underlying your sum is not a particular one, then there is no shorcut to evaluate your sum. – Olivier Oloa Jan 2 '18 at 17:10