Efficient way to compute p^q (exponentiation), whe

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

Answer 2

Assuming that ^ means exponentiation and that q is runtime variable, use std::pow(double, int).

EDIT: For completeness due to the comments on this answer: I asked the question Why was std::pow(double, int) removed from C++11? about the missing function and in fact pow(double, int) wasn't removed in C++0x, just the language was changed. However, it appears that libraries may not actually optimize it due to result accuracy concerns.

Even given that I would still use pow until measurement showed me that it needed to be optimized.

Answer 3

I assume by ^ you mean power function, and not bitwise xor.

The development of an efficient power function for any type of p and any positive integral q is the subject of an entire section, 3.2, in Stepanov's and McJones's book Elements of Programming. The language in the book is not C++, but is very easily translated into C++.

It covers several optimizations, including exponentiation by squaring, conversion to tail recursion then iteration, and accumulation-variable elimination, and relates the optimizations to the notions of type regularity and associative operations to prove it works for all such types.