c++ - 计算 p^q（取幂）的有效方法，其中 q 是整数

Question

^{什么是计算 p q}的有效方法，其中 q 是整数？

Answer 1

通过平方求幂仅使用 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（但像往常一样，在计算绝对值时要小心）。

Answer 2

假设这^意味着取幂并且q是运行时变量，请使用std::pow(double, int).

编辑：由于对此答案的评论，为了完整性：我问了为什么 std::pow(double, int) 从 C++11 中删除的问题？关于缺少的功能，实际上pow(double, int)并没有在 C++0x 中删除，只是语言被改变了。但是，由于结果准确性问题，库似乎实际上并未对其进行优化。

即使考虑到我仍然会使用pow，直到测量表明我需要对其进行优化。

Answer 3

我假设 ^ 你的意思是幂函数，而不是按位异或。

任何类型的 p 和任何正积分 q的有效幂函数的开发是Stepanov 和 McJones 的书Elements of Programming中整个 3.2 节的主题。书中的语言不是 C++，但很容易翻译成 C++。

它涵盖了几种优化，包括通过平方求幂、转换为尾递归然后迭代和累积变量消除，并将优化与类型正则性和关联操作的概念联系起来，以证明它适用于所有这些类型。