0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ tell the reason for downvoting. $\endgroup$ – rock321987 Nov 3 '15 at 9:37
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – rock321987 Nov 3 '15 at 9:34
  • 1
    $\begingroup$ 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$. $\endgroup$ – achille hui Nov 3 '15 at 10:36
  • $\begingroup$ thanks..first doubt was silly $\endgroup$ – rock321987 Nov 3 '15 at 10:48

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.