how to compute 'y' in 2^y = 2^q0 + ... + 2^qn efficiently in C++?

Question

I have equation:

2^y = 2^q0 + ... 2^qn

n is a arbitrary integer number(there are arbitrary number of 'q's). the value for 'q's can be as big as 500 which 2^q couldn't store in integer or long variable types. I want to compute 'y' other than the method below, because of storage capacity problem :

log2(2^q0 + ... + 2^qn)

how can i compute 'y' in efficient way in C++. is there anyway to compute 'y' with simple arithmetic operations on 'q's ?!

EDIT: 'q's are non negative, I look for 2 versions of this problem: 'q's are integer, 'q's are double

Answer 1

First sort qis. Let's say minimum is p, subtract p from all qis. You may check if the qis form a Arithmetic serie, if you're lucky and they form such serie, you have a mathematical shortcut, but otherwise since AFAIK there is no mathematical rule to simplify log(a1 + a2 + ... + ak) the best way to compute y is this:

Since you have qis sorted, you can compute sum = 1 + 2 ^ (q1-p) + 2 ^ (q2-p) + ... in a dynamic-algorithm-like way(i.e using previous results to compute next term).

prev_exp = 0;
prev_term = 1;
this_term = 0;
sum = 1;
// p is previously subtracted from q[i]s
for (int i = 1; i < n; ++i) {
  this_term = prev_term * (1 << (q[i] - prev_exp)); // 2 ^ m = (1 << m)
  prev_term = this_term;
  prev_exp = q[i] - prev_exp;
  sum += this_term;
}

y can be computed as y = p + log2(sum)

Note that you are also summing the small numbers first. That will help floating point precision.

I was editing this answer to add another solution based on divide-and-conquer type of algorithms but i couldn't finish it, but i guess if i leave it in a hidden block(spoiler block in this site's editor naming) somebody can finish off or improve this part of answer. feel free to edit.

In case of maximum of q[i]s is so larger than minimum of them(i.e p), you can use divide and conquer algorithm, recursively compute sum1 = 1 + 2^(q[1]-p) + .... + 2^(q[n/2]-p) and sum2 = 2^(q[n/2 + 1]-p) + ... + 2 ^ (q[n-1] - p) you can factorize 2^(q[n/2 + 1]-p) here too. then you'll have: y = p + log2(sum1 + sum2) = p + log2(sum1 + 2^p' sum2') where p' is q[n/2 + 1]-p. It helps you to keep your numbers smaller.