计算p ^ q（取幂）的有效方式，其中q是整数 [英] Efficient way to compute p^q (exponentiation), where q is an integer

问题描述

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

What is an efficient way to compute p^q, where q is an integer?

推荐答案

通过平方的指数仅使用O（lg q ）乘法。 p>

Exponentiation by squaring uses only O(lg q) multiplications.

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 ，运算符* ）其中从 1 构造的 T 是标识元素。

This should work on any monoid (T, operator*) where a T constructed from 1 is the identity element. That includes all numeric types.

将此扩展为 signed q 很容易：只需将结果除以上面的 q 的绝对值（但像往常一样，在计算绝对值时要小心）。

Extending this to signed q is easy: just divide one by the result of the above for the absolute value of q (but as usual, be careful when computing the absolute value).

这篇关于计算p ^ q（取幂）的有效方式，其中q是整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！