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$?

  • 1
    $\begingroup$ you can find your second and third sum by an simple (numeric) derivative w.r.t. $a$ $\endgroup$ – tired Jan 2 '18 at 14:49
  • $\begingroup$ 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.) $\endgroup$ – Semiclassical Jan 2 '18 at 14:51
  • $\begingroup$ 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. $\endgroup$ – 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$.

If one knows the value of a polynomial at some real number and all its derivatives at the same real number how one may obtain its value at another real number?

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$.

  • $\begingroup$ 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. $\endgroup$ – Luc Jan 2 '18 at 15:47
  • $\begingroup$ 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. $\endgroup$ – Olivier Oloa Jan 2 '18 at 17:10

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.