1
$\begingroup$

In my work, I had to essentially compute the following quantity.

Given a sequence of positive floating point numbers $\{a_i\}_{i=1}^n$, such that

$$6000 \leq a_i \leq 7000$$

I needed to compute the following quantity (for some $n>1$, but for now can assume $n=1000$):

$$\log_2\left(\frac{\sum_{i=1}^n 2^{a_i}}{n}\right)$$

Direct computation is infeasible as the exponents are too large. So I rewrote the above expression as $$a_1 + \log\left(\frac{1+\sum_{i=2}^n 2^{a_i-a_1}}{n}\right)$$

This also seemed a bit daunting but was better than what I had. My question was, is there a better way/algorithm to compute the above quantity? I appreciate any help on this.

The following observation might help:

$$\frac{\sum_{i=1}^n a_i}{n}\leq \log_2\left(\frac{\sum_{i=1}^n 2^{a_i}}{n}\right)\leq \max_{1 \leq i \leq n} a_i$$

$\endgroup$
  • 1
    $\begingroup$ I can improve your observation: a better lower bound is $a_i - \log n$. $\endgroup$ – Yuval Filmus Jul 25 '17 at 20:26
  • $\begingroup$ Now that I think about it, that will get you matching upper and lower bounds differing only by log n. Thanks. You have given me an excellent way to approach my original problem. $\endgroup$ – K Gautam Shenoy Jul 25 '17 at 21:29
3
$\begingroup$

Let $a = \max_i a_i$. Then your expression is equal to $$ a + \log_2 \frac{\sum_i 2^{a_i-a}}{n}, $$ and this should be a very good approximation (this is "renormalization"). Don't forget to add the numbers in decreasing order of magnitude (that is, sort the $a_i$'s so that they are in decreasing order).

$\endgroup$
  • $\begingroup$ I must say that this is an excellent trick to calculating this value. If $a_i-a$is large, then the corresponding exponential will be very small and can be ignored. If it is small, the exponential is computable!! My MATLAB computations indicate towards this as well. This deserves to be amongst the best but simple techniques in computer science. $\endgroup$ – K Gautam Shenoy Mar 20 '18 at 7:23

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.