计算 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;
}

这应该适用于任何 monoid (T, operator*< /code>)，其中由 1 构造的 T 是单位元素。这包括所有数字类型。

将其扩展到 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 的《编程元素》一书中的整个章节 3.2。书中的语言不是C++，但很容易翻译成C++。

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