gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-02 23:09:41 28 4
gpt4 key购买 nike

我有等式:

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

最佳答案

首先对 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。它可以帮助您减少数字。

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

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com