我有等式：
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是双
解决方法
首先排序qis.假设最小值是p,从所有q减去p.你可以检查qis是否形成算术系列,如果你很幸运并且他们形成了这样的系列,你有一个数学捷径,但是否则因为AFAIK没有数学规则来简化log(a1 a2 … ak)最好计算y的方法是这样的：
由于您已经对qis进行了排序,因此您可以以类似动态算法的方式计算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 / 21] -p)… 2 ^(q [n-1] – p)你可以分解2 ^(q [n / 2 1] -p)这里也.然后你会有：y = p log2(sum1 sum2)= p log2(sum1 2 ^ p’south2′)其中p’是q [n / 2 1] -p.它可以帮助您减少数字.
