什么是计算 p q的有效方法,其中 q 是整数?
问问题
6748 次
3 回答
43
通过平方求幂仅使用 O(lg q ) 乘法。
template <typename T>
T expt(T p, unsigned q)
{
T r(1);
while (q != 0) {
if (q % 2 == 1) { // q is odd
r *= p;
q--;
}
p *= p;
q /= 2;
}
return r;
}
这应该适用于构造自是标识元素的任何幺半群( T
, operator*
) 。这包括所有数字类型。T
1
将其扩展到signed q
很容易:只需将 1 除以上述结果即可得到绝对值q
(但像往常一样,在计算绝对值时要小心)。
于 2011-04-11T18:01:09.953 回答
12
假设这^
意味着取幂并且q
是运行时变量,请使用std::pow(double, int)
.
编辑:由于对此答案的评论,为了完整性:我问了为什么 std::pow(double, int) 从 C++11 中删除的问题?关于缺少的功能,实际上pow(double, int)
并没有在 C++0x 中删除,只是语言被改变了。但是,由于结果准确性问题,库似乎实际上并未对其进行优化。
即使考虑到我仍然会使用pow
,直到测量表明我需要对其进行优化。
于 2011-04-11T18:01:06.377 回答
9
我假设 ^ 你的意思是幂函数,而不是按位异或。
任何类型的 p 和任何正积分 q的有效幂函数的开发是Stepanov 和 McJones 的书Elements of Programming中整个 3.2 节的主题。书中的语言不是 C++,但很容易翻译成 C++。
它涵盖了几种优化,包括通过平方求幂、转换为尾递归然后迭代和累积变量消除,并将优化与类型正则性和关联操作的概念联系起来,以证明它适用于所有这些类型。
于 2011-04-11T18:07:56.637 回答