The Power Algorithm
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
n times, but of course the idea is to provide an algorithm
that’s faster than this. The algorithm in question is usually called
the binary method, the powering ladder or the repeated-squaring
Say we want to calculate
x = 2 and
n = 23 this
algorithm takes into account the binary representation of
10111), scans it and depending if it finds a
0 or a
1 it will
x or multiply by
The problem with this method is that it scans the binary representation of the number from left to right, but for computers it’s usually easier to do it the other way around, so Knuth proposes a alternative algorithm.
A simple implementation of Algorithm A from section 4.6.3 of TAOCP is as follow:
This function takes two integers,
$n and returns
the power of
First it sets an auxiliary variable
1 which is the identity
of the multiplication.
Then the function scans the binary representation of
$n on each
iteration of the loop. If it finds a
1 then it multiplies by
$x. On every step of the loop it squares
Finding a 1 means that the current value of
$n is not divisible by
2, or in other words,
$n % 2 == 1.
Also on every iteration of the loop
$n gets halved and then we apply
floor to the result. When
0, we terminate the loop and
return the value of
power can be called like this:
At this point I imagine you being like the guy on this gif:
While the algorithm really looks like a CSB, it is actually quite effective when it comes to computing with very big numbers. For example there are many primality testing algorithms that depend on variations of this algorithm.
Adding some abstraction
So far nothing fancy, but if we notice that raising a number to a
power is actually the same as multiplying the number by itself that
many times, we could also see that multiplication is the same as
adding a number by itself that many times. So for example
2 * 5
could be computed by doing
2 + 2 + 2 + 2 + 2.
Can we convert our algorithm into a more generic form that would work for multiplication and addition? Of course we can. We just need to change a couple of things.
On the current implementation we set
$y to the identity element of
1. If we want to use the algorithm for
addition, then we need to set
0. So we could just pass the
value of our identity element to the function.
The second step would be to provide a function to our algorithm that
would do either multiplication or addition. To do that we will pass a
function that will act as a binary operation, i.e.: a function that
takes two arguments. This function needs to follow some rules as well,
that is, it has to be associative:
a• (b • c) = (a • b) •. Also the
type of the result value must be the same type as both input
Luckily for us addition and multiplication are associative operations,
so we can just wrap them in a function and pass it to our
Here’s the new implementation of the algorithm:
And we can call it like this:
As you can see there we passed
1 as our identity element, and we
provided a function that takes
2 arguments and returns the result of
their multiplication. Nothing fancy.
But now say we want to calculate
2 * 10 using our algorithm. We
could wrap the addition operator inside a function and then pass
the identity element like this:
Keep in mind that the operation that we pass to our algorithm must be
associative, for example, subtraction can’t be used here since for
10 - (5 - 3) = 8 while
(10 - 5) - 3 = 2.
Appending more abstraction
Mathematically speaking this algorithm works with any algebraic structure that has an associative operation (like multiplication and addition in the case of integers), that is, it works on Semigroups. To quote a book on Group Theory:
A semigroup set S equipped with an associative binary operation •; that is, x • (y • z) = (x • y) • z for all x, y, z ∈ S.
Also, that set must have an identity element, which makes it a Monoid:
A monoid is a set M equipped with an associative binary operation •; together with an identity element e ∈ M that satisfies e • x = x • e = x for all x ∈ M.
What other structures that we use every day in programming can work
under the previous conditions? If you are a web developer you don’t
need to dig so much to find strings. Strings, using string append as
the binary operation and the empty string as the identity element
would give use similar results as above. If we wanted to repeat a
n times, we could create the following function:
And to test it:
Now think about arrays (or lists in other languages). We could want to
build an array with
n copies of the same element. Here the empty
array is the identity element, and in the case of PHP array_merge
would be our binary operation.
And here are our results:
As you can see here, something that seemed so simple as raising a number to a certain power gave us a neat algorithm that can be used for several things, like repeating strings or elements inside an array.
The power algorithm as implemented here is based on TAOCP, Vol II, section 4.6.3.
The whole explanation of how this works can be found in TAOCP or in the book A Computational Introduction to Number Theory and Algebra. The PDF of the book is freely available on the author’s website. Look into section “Computing with large integers - The repeated squaring algorithm”.
If you would like to learn about several uses for this algorithm and some more theory behind it, then consult the book called Elements of Programming. This book is great in the way it defines the different types of functions, and how it uses the type system to be sure that the function is actually associative, binary, and so on. The author is the designer of C++ STL, so while the concerns of the book might seem very theoretical, then can be directly applied in OOP programs.
The quotes about Semigroups and Monoids are from the book Handbook of Computational Group Theory. A very interesting book if you are into CGT.
If you want to learn more about Monoids and their implementations this chapter from Learn You a Haskell has a very nice introduction to Functors, Applicative Functors and Monoids.
It could be an interesting exercise to implement these concepts using say PHP and OOP, or for the PHP non lovers, in some other imperative language of your choice.
Did you just say Haskell?
Since I’ve mentioned a Haskell book, here’s an implementation of the power algorithm in Haskell, using a recursive algorithm based on the book Prime Numbers: A Computational Perspective.
And here are the results of several invocations of the function:
As you can see there, the function takes a function
(a -> a -> a)
which could be either
+ for integers, or
++ for lists, for
I hope you found this blog post interesting, and that I have whetted your appetite for learning maths in relation to programming, since I think the more we grasp these ideas, the better the abstractions we would be able to use.