# How to find the solution to this summation

This was a question asked in our exam and we have to write a code for it. We have to find the summation of following series

$\log(\sum_1^n (e^{x_i}))$

where $1 < n < 10^6$ and $0 < x_i < 10^6$

For this series if we have to calculate the summation for $n = 2$, there can be a case like $e^{10^6} + e^{10^4}$ that will easily exceed the value of any data type. One obvious solution was to apply string multiplication and addition but it would also be time consuming. I want to know is there any mathematical formula for calculating this series or any other method to find the summation?

• tell the reason for downvoting. – rock321987 Nov 3 '15 at 9:37

For simplicity, consider the case $x_i$ are sorted in descending order.

$$x_1 \ge x_2 \ge x_3 \ge \cdots$$

Let $M = x_1 = \max\limits_{1\le i \le n}\{ x_i \}$, we have $$\log \sum\limits_{i=1}^n e^{x_i} = M + \log\sum\limits_{i=1}^n e^{x_i-M} = M + \log\left(1 + \sum_{i=2}^n e^{x_i-M}\right)$$ For any $\Lambda > 0$, let $m$ be a index such that

$$M = x_1 \ge x_2 \ge \cdots \ge x_m \ge \Lambda \ge x_{m+1} \ge \cdots x_n$$

Using the fact for $x, y \ge 0$, $|\log(1+x) - \log(1+y)| \le |x-y|$, we have

$$\left|\log\left(1 + \sum_{i=2}^n e^{x_i-M}\right) -\log\left(1 + \sum_{i=2}^m e^{x_i-M}\right)\right| \le \sum_{i=m+1}^n e^{x_i-M} \le n e^{-\Lambda}$$

This means given any $\epsilon > 0$, if we set $\Lambda = \log\left(\frac{n}{\epsilon}\right)$, we have

$$\left|\log\sum_{i=1}^n e^{x_i} - \left(M + \log\left(\sum_{\substack{i=1,\\M - x_i \le \Lambda}}^{n} e^{x_i-M}\right)\right) \right| \le \epsilon$$

If one want to compute the log of sum accurate to some $\epsilon$, one don't need to carry the whole sum inside the log. Instead, one just need to sum over a small subset of $x_i$ which satisfies $M - x_i \le \Lambda$.

For example, let's say $n = 10^6$ and $\epsilon = 10^{-12}$, the corresponding $\Lambda = 18\log(10) \approx 41.4465$. a number much smaller than the possible ranges of $x_i$.

• i am having two doubts i)$\log \sum\limits_{i=1}^n e^{x_i} = M + \log\sum\limits_{i=1}^n e^{x_i-M}$ (how?) ii)$\Lambda = \log\left(\frac{n}{\epsilon}\right)$ (why?) – rock321987 Nov 3 '15 at 9:34
• 1) $\log\sum_i e^{x_i} = \log(e^M \times (\sum_i e^{x_i-M}))$ 2) we want $n e^{-\Lambda} \le \epsilon \iff \frac{n}{\epsilon} \le e^\Lambda \iff \log\frac{n}{\epsilon} \le \Lambda$. – achille hui Nov 3 '15 at 10:36
• thanks..first doubt was silly – rock321987 Nov 3 '15 at 10:48