Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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

like image 759
q0987 Avatar asked Apr 11 '11 18:04

q0987


1 Answers

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

like image 137
Fred Foo Avatar answered Sep 29 '22 10:09

Fred Foo