My latest posts can be found here:
Previous blog posts:
Additionally, some earlier writings:
Russian Peasant Multiplication - 2015/05/18
Sometimes simply called "Peasant Multiplication," sometimes called "Ancient Egyptian multiplication," sometimes called "Ethiopian multiplication," sometimes called "Multiplication by Doubling and Halving," this algorithm is well-known to some, a mystery to others, and more useful than you might think, being applicable not just to multiplication of numbers, but also useful for exponentiation, and for matrices.
This is described in detail in lots and lots of places, and a simple search for any of the above terms will turn up many references, but there are a few things I haven't seen elsewhere, so even if you have seen this before, I hope to show you something new.
When the number in the left column is odd we add the number in the second column into the running total. That's why the third column starts with a (possibly implicit) 0.
Next, we halve the number in the left column, discarding any remainder. In this case we halve 13 to get 6. Then we double the number in the second column, in this case going from 19 to 38.
The number in left column is now even, so we don't do any addition into the running total.
Repeat. Halve the left, double the middle. Now we have 3 in the left column, which is odd, so we add the 76 to the 19 giving 95.
Proof that it works
So the first question is why this works. Some people will say that it is just the usual long multiplication technique done in binary, and that's true. However, there is another explanation which is longer, but opens the door to a generalisation or two. We look at this with the aid of an invariant.
This will seem complicated, but it's more detailed than complicated. The technique of proof is important - you'll see that in the next section.
So call the number in the first column A, the second column B, the running total R, and the answer we want P (for product). With the way we've set things up, the following is true:
Now if A is even then A=2k for some k. So we can write this as:
And that, of course, is the same as:
So if we replace A with half its value, and B with double its value, and call those A' and B' then we have:
In other words, when A is even, we can halve the first number and double the second, and our condition is still true. What about when A is odd? Then we can write A=2k+1 for some k. Things are a little messier now. To make things simpler I'll use the usual convention that multiplication is done before addition, that way I can omit most of the brackets. Also, writing things immediately next to each other means "multiply these", so I can use brackets and the "." to emphasise what's going on:
But when we finish, the number in the first column is 0. Then we have
Or simply R=P. Our running total is the (previously unknown) product that we wanted.
Generalisation 1: Exponentiation
So now let's generalise this to compute 213. In exponentiation we multiply things together as opposed to adding them, so we generalise the technique by:
Next step: 6 is even so don't multiply into our running total. Then halve the 6 and square the 4 to get 16.
Now 3 is odd, so multiply 16 into the running product to give 32. Then halve the first column and square the second.
Final step: 1 is odd, so multiply 256 by 32 to give 8192, which is our final answer.
The cool thing is that the proof we have above works for this too. Our invariant is now:
where E is our desired exponentiation. Using that invariant, the proof goes through with minor modifications and is left as an exercise for the mythical interested reader.
Generalisation 2: Matrices
Here is the exponentiation routine coded in Python. It works for any non-negative integer exponent, and any "base" that is of a type that supports multiplication, and where that multiplication is associative. In other words, it works for any collection with a multiplication that forms a monoid.
But you don't need to know that, all you need to know is that it works for matrices, and that's what we'll use to speed up our calculation of Perrin numbers.
To save you the effort of looking it up yourself, here are the searches for the algorithm on-line, and the wikipedia page:
I've decided no longer to include comments directly via the Disqus (or any other) system. Instead, I'd be more than delighted to get emails from people who wish to make comments or engage in discussion. Comments will then be integrated into the page as and when they are appropriate.
If the number of emails/comments gets too large to handle then I might return to a semi-automated system. That's looking increasingly unlikely.
Links on this page