What is an efficient way to compute pq, where q is an integer?
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).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With