# power

 Category: algorithms Component type: function

## Prototype

`Power` is an overloaded name; there are actually two `power` functions.

```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);
```

## Description

`Power` is generalized exponentiation: it raises the value `x` to the power `n`, where `n` is a non-negative integer.

The first version of `power` returns `x` raised to the `n`th power; that is, it returns `x * x ... * x`, where `x` is repeated `n` times. [1] If `n == 0`, then it returns `MonoidOperation(multiplies<T>())`.

The second version of `power` is just like the first except that it uses an arbitrary MonoidOperation instead of `multiplies<T>`, returning `MonoidOperation(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]

## Definition

Defined in the standard header numeric, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.

## Requirements on types

For the first version:

• `multiplies<T>` is a model of MonoidOperation.
• `Integer` is an integral type.

For the second version:

• `MonoidOperation` is a model of MonoidOperation.
• `T` is `MonoidOperation`'s argument type.
• `n` is an integral type.

## Preconditions

• `n >= 0`.

## Complexity

The number of multiplications (or, in the case of the second version, the number of applications of `MonoidOperation`) is `lg(n) + nu(n)` where `lg` is the base 2 logarithm and `nu(n)` is the number of `1`s in the binary representation of `n`. [3]

## Example

```int main() {
cout << "2 ** 30 = " << power(2, 30) << endl;
}
```

## Notes

[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 MonoidOperation 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.

MonoidOperation, `multiplies`, `plus`