Category: algorithms | Component type: function |
template <class T, class Integer> inline T power(T x, Integer n); template <class T, class Integer, class MonoidOperation> T power(T x, Integer n, MonoidOperation op);
The first version of power returns x raised to the nth power; that is, it returns x * x ... * x, where x is repeated n times. [1] If n == 0, then it returns identity_element(multiplies<T>()).
The second version of power is just like the first except that it uses an arbitrary Monoid Operation instead of multiplies<T>, returning identity_element(op) when n == 0.
Important note: power does not assume that multiplication is commutative, but it does rely crucially on the fact that multiplication is associative. If you have defined * or MonoidOperation to be a non-associative operation, then power will give you the wrong answer. [2]
int main() { cout << "2 ** 30 = " << power(2, 30) << endl; }
[1] This is a conceptual description of what power's return value is; it is not how power is actually implemented. If power were implemented that way then it would require n-1 multiplications, which would be grossly inefficient. Power is implemented using the "Russian peasant algorithm", which requires only O(log n) multiplications. See section 4.6.3 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, Addison-Wesley, 1981) for a discussion.
[2] See the Monoid Operation requirements for a discussion of associativity.
[3] This is in fact not the minimum possible number of multiplications: it is possible to compute the fifteenth power of x using only five multiplications, but power(x, 15) uses six.