c++ - 如何在C++中有效地计算2 ^ y = 2 ^ q0 +…+ 2 ^ qn中的 'y'？

我有方程式:

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

n是任意整数(“q”有任意数量)。 “q”的值可以大到500，而2 ^ q不能以整数或长变量类型存储。由于存储容量问题，我想计算以下方法以外的“y”:

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

我如何在C++中以有效的方式计算“y”。无论如何，是否可以通过对'q'的简单算术运算来计算'y'？

编辑:'q是非负的，我寻找这个问题的2个版本:'q是整数，'q是 double

最佳答案

首先对qi排序。假设最小值为p，然后从所有p中减去qi。您可以检查qi是否构成算术序列，如果很幸运并且它们构成这样的序列，则具有数学上的捷径，但是否则，由于AFAIK没有简化log(a1 + a2 + ... + ak)的数学规则，因此计算y的最佳方法是:

由于已对qi进行了排序，因此您可以采用类似于动态算法的方式来计算sum = 1 + 2 ^ (q1-p) + 2 ^ (q2-p) + ...(即，使用先前的结果来计算下一项)。

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可以计算为y = p + log2(sum)
请注意，您还要先对小数字求和。这将有助于浮点精度。

我正在编辑此答案以添加另一种基于分而治之算法的解决方案，但我无法完成它，但是我想我是否将其保留在隐藏的块中(本网站的编辑器命名中的破坏块)，有人可以完成关闭或改善这部分答案。随时进行编辑。

如果q[i]的最大值大于它们的最小值(即
p)，可以使用分治法，递归计算
sum1 = 1 + 2^(q[1]-p) + .... + 2^(q[n/2]-p)和sum2 = 2^(q[n/2 + 1]-p) + ... + 2 ^ (q[n-1] - p)您可以分解2^(q[n/2 + 1]-p) 这里也。那么您将拥有:

y = p + log2(sum1 + sum2) = p + log2(sum1 + 2^p' sum2')其中p' 是q[n/2 + 1]-p。它可以帮助您保持较小的数字。

关于c++ - 如何在C++中有效地计算2 ^ y = 2 ^ q0 +…+ 2 ^ qn中的 'y'？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20562185/