`Notes`

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

Loading...