c++ - 如何在 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's 是非负数，我寻找这个问题的 2 个版本:'q's 是整数，'q's 是双数

Answer 1

首先对 qi 进行排序。假设最小值是 p，从所有 qi 中减去 p。你可以检查 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)

请注意，您还首先对小数求和。这将有助于浮点精度。

我正在编辑这个答案以添加另一个基于分而治之算法的解决方案，但我无法完成它，但我想如果我把它留在一个隐藏的 block 中(本网站编辑器命名中的剧透 block )有人可以完成或改进这部分答案。随意编辑。

如果 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。它可以帮助您减少数字。