17

什么是计算 p q的有效方法,其中 q 是整数?

4

3 回答 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*) 。这包括所有数字类型。T1

将其扩展到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 回答