计算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*),其中T构造的1是标识元素.这包括所有数字类型.

将其扩展signed q为简单:只需将上面的结果除以一个绝对值q(但通常在计算绝对值时要小心).

Answer 2

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

编辑:为了完整性,由于对这个答案的评论:我问的问题为什么从C++ 11中删除了std :: pow(double,int)？关于缺失的函数,实际上pow(double, int)没有在C++ 0x中删除,只是语言被更改了.但是,由于结果准确性问题,图书馆似乎无法实际优化它.

即使考虑到我仍然会使用,pow直到测量显示我需要进行优化.

Answer 3

我假设你的意思是幂函数,而不是按位xor.

任何类型的p和任何正整数q的高效幂函数的开发是Stepanov和McJones的书"编程元素"中的整个部分3.2的主题.本书中的语言不是C++,但很容易翻译成C++.

它包括几个优化,包括通过平方取幂,转换为尾递归然后迭代,以及累积变量消除,并将优化与类型规则性和关联运算的概念联系起来,以证明它适用于所有这些类型.