c++ - Efficient way to compute p^q (exponentiation), where q is an integer

Question

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

Answer 1

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

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

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).