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

Question

我有等式:

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是双

Answer 1

第一种qi.假设最小值是从所有s中p减去.你可以检查s是否形成算术系列,如果你很幸运并且他们形成了这样的系列,你有一个数学捷径,但是否则因为AFAIK没有数学规则来简化计算的最佳方法是这样的:pqiqilog(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]s 的最大值大于它们的最小值(即 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.它可以帮助您减少数字.