Efficient way to calculate p ^ q (exponential), where q is an integer

Question

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

Answer 1

Exposure by squaring uses only O (log q) multiplication.

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 with any monoid ( T , operator* ), where a T constructed from 1 is an identity element. This includes all numeric types.

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

Answer 2

Assuming ^ means exponentiation and that q is a run-time variable, use std::pow(double, int) .

EDIT: for completeness, due to comments on this question: I asked the question Why is std :: pow (double, int) removed from C ++ 11? about the missing function and actually pow(double, int) not deleted in C ++ 0x, only the language was changed. However, it seems that libraries cannot actually optimize it due to problems in terms of accuracy.

Even considering that I will still use pow until the measurement shows me that it needs to be optimized.

Answer 3

I assume that you mean the power function, not the bitwise xor.

The development of an effective force function for any type p and any positive integral q is the subject of the entire section 3.2, in the book by Stepanov and MacJon Programming Elements . The language in the book is not C ++, but very easily translated into C ++.

It covers several optimizations, including exponentiation, squaring, transforming to tail recursion, then iterating and eliminating exceptions during the accumulation process, as well as linking optimizations to concepts of type regularity and associative operations to prove that it works for all such types .