The Power Algorithm

The Power Algorithm March 19 2014 In this blog post I would like to show how a very basic idea like raising a number to a certain power could lead us to discover abstractions like Semigroups and Monoids. There’s a very well known algorithm for calculation powers, that is x to the power of n or simply: x^n . Donald Knuth presents the algorithm in section 4.6.3 Evaluation of Powers of TAOCP. The naïve way to implement this algorithm would be to multiply x by itself n times, but of course the idea is to provid