How to efficiently calculate "y" in 2 ^ y = 2 ^ q0 + ... + 2 ^ qn in C ++?

Question

I have an equation:

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

n is an arbitrary integer (there is an arbitrary number "q"). the q value can be as large as 500, which 2 ^ q could not be stored in integer or long variable types. I want to calculate "y", except for the method below, due to a capacity problem:

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

how can I efficiently calculate "y" in C ++. anyway, to compute "y" with simple arithmetic operations on "q ?!

EDIT: q are not negative, I am looking for two versions of this problem: "q is an integer", q is double

Answer 1

First sort qi s. Let say min p , subtract p from all qi s. You can check if qi form of arithmetic series, if you are lucky and they form such a series, you have a math shortcut, but otherwise with AFAIK there is no math rule to simplify log(a1 + a2 + ... + ak) , the best way to calculate y :

Since you have qi sorted, you can calculate sum = 1 + 2 ^ (q1-p) + 2 ^ (q2-p) + ... in a way similar to a dynamic algorithm (for example, using the previous results to calculate the 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 calculated as y = p + log2(sum)

Note that you sum small numbers first. This will help floating point precision.

I edited this answer to add another solution based on the type of divide-and-conquer algorithms, but I could not finish it, but I think if I leave it in a hidden block (the spoiler block in the name of this site editor) someone can complete or improve this part of the answer. Feel free to edit.

In the case of maximum q[i] so much more than the minimum of them (ie p ), you can use the division and conquest algorithm, recursively calculate 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 expand the factorization 2^(q[n/2 + 1]-p) here too. then you will have: y = p + log2(sum1 + sum2) = p + log2(sum1 + 2^p' sum2') where p' q[n/2 + 1]-p . This will help you keep your numbers smaller.

Answer 2

This is clearly a problem that cannot be provided inside standard or built-in types.

You may notice that 2 ^ qx is 1 left qx bit shifted, and log2 (y) is the number of right shift that you must accept before the number becomes one. You may then notice that adding two numbers to the overflow makes the result smaller than the added ns and 1 to multiply on the left.

At this point you can:

• implement a class that stores 500 bits (you can use unsigned x[1+500/sizef(unsigned)]) )
• give this class an explicit constructor taking unsigned q that sets the corresponding bit (divides q by sizeof (unsigned) to determine the index, and use modular to determine the remaining shift)
• implement the + operator for your "big interger" (just sum the subintegers starting with the last one, and spread the hyphenation, if any, that is: if the sum is less than the terms)
• perform log2 operation, counting the position of the highest level 1.

---

In case you can guarantee that the various qi are not repeated, there is no need for such arithmetic: all you need to do is just remember the highest.

Answer 3

You do not need to take powers or multiply in order to take the integral power 2: just shift 1 by the corresponding amount. I think the following code will be most effective:

 double ComputeY( vector<unsigned> Qs ) { unsigned sum = 0; for( vector<unsigned>::iterator it = Qs.begin(); it != Qs.end(); ++it ) { int q = *it; // Get the next q int two_power_q = 1 << q; // This is the key: 2^q == 1 << q sum += two_power_q; } double y = log2( sum ); // need double because the result may not be integer return y; } 

Answer 4

This solution is similar to the MJafar Mash solution, but avoids infinity (for example: if the neighboring indicators have a huge difference {0, 1024}).

 #include <algorithm> #include <cmath> #include <iostream> #include <limits> #include <vector> #include <iostream> #include <type_traits> template <typename T> double logarithm(const std::vector<T>& sorted_exponents) { typedef typename std::make_unsigned<T>::type Unsigned; const unsigned digits = 32; // Evaluate sum(2^sorted_exponents[i]) = sum * 2^scale*digits double sum = 0; Unsigned scale = 0; for(Unsigned e : sorted_exponents) { // Evaluate e = 2^e * 2^(s*digits) Unsigned s = e / digits; e %= digits; sum = double(uint32_t(1) << e) + sum / pow(2.0, double(s - scale)*digits); scale = s; } return std::log2(sum) + double(scale)*digits; } int main() { std::cout.precision(std::numeric_limits<double>::digits10 + 1); std::vector<int> v; unsigned size = 500; for(unsigned max_exponent = 1; max_exponent < 10000000; max_exponent *= 10) { v.clear(); v.reserve(size); for(unsigned i = 0; i < size; ++i) v.push_back(std::rand() % max_exponent); std::sort(v.begin(), v.end()); double log = logarithm(v); std::cout << "Maximal Exponent: " << v.back() << std::endl; std::cout << " Logarithm: " << log; std::cout << std::endl; } } 

Result:

 Maximal Exponent: 0 Logarithm: 8.965784284662087 Maximal Exponent: 9 Logarithm: 15.58590144969077 Maximal Exponent: 99 Logarithm: 102.4678312951325 Maximal Exponent: 997 Logarithm: 997.5899323737988 Maximal Exponent: 9999 Logarithm: 9999.000000002708 Maximal Exponent: 99960 Logarithm: 99960.32192809488 Maximal Exponent: 998055 Logarithm: 998055 

Answer 5

digest what is asked here.

  qn binary 2^0 => 00000001 2^1 => 00000010 2^2 => 00000100 --------------- sum => 00000111 y => log2(sum) => 2 

This means that he asks where the position of the leftmost binary 1 is after summing all 2 ^ q0 + ... 2 ^ qn
and qn is the position of the binary digit 1 in each 2 ^ qn.

Others pointed out that if everything in q is unique, y = max_element (q).

If this is not the case, we must calculate the sum and find the left most binary digit 1. To calculate the sum, we do not need to save the whole digit, only the left most.

Convert each 2 ^ qn to binary and group each element of q where it falls into digit 1. If digit 1 falls into the first 48 digits, put it in group 0, if it falls in the second 48-digit digit, put it in a group 1 and so on. Then we calculate the sum of group 0 and transfer all the overflow numbers to the next group until we calculate the last group.

A group of 48 digits is selected so that it can be calculated using int64 with bit 8 of the MSB as carrie forward.
In the last group, find the position of the leftmost digit 1: left_most_bit .
Then the value y = left_most_bit + group_number * 48

 int function(vector<int> const& q) { vector<int> group; // group each element in q for(int i=0; i<q.size(); ++i) { group[i] = q[i] / 48; } // find the maximum group int group_max = std::max_element(group.begin(), group.end()); int64 sum = 0; for(int g=0; g<=group_max; ++g) { // calculate group of 48 bits for(int i=0; i<q.size(); ++i) { if(group[i] == g) // is this elementin the group that we are calculating? { int pos_of_digit_1 = q[i] - g * 48; sum += (1 << pos_of_digit_1); // convert to value and sum it. } } sum = sum >> 48; // carrie forward the 8 MSB bits } int pos_of_left_most_1 = 0; for(int i=0; i<64; ++i) { if((sum << i) & 0x8000000000000000); { pos_of_left_most_1 = 64 - i; break; } } return group_max * 48 + pos_of_left_most_1; } 

This answer is for integer values ​​of y and q. For a floating point value, we cannot do this.