Subscribe!

• Colins Blog

• FindingPerrinPseudoPrimes Part2
• FindingPerrinPseudoPrimes Part1
• The Unwise Update
• Miles Per Gallon
• Tracking An Item On Hacker News
• Hacker News User Ages
• Poking The Dusty Corners
• There Is No Time For This
• Publically Sharing Links
• Learning Times Tables
• Graceful Degradation
• Diagramming Maths Topics
• On The Rack
• Square Root By Long Division
• Beyond The Boundary
• Fill In The Gaps
• Software Checklist
• NASA Space Crews
• The Birthday Paradox
• The Trapezium Conundrum
• Revisiting The Ant
• The Ant And The Rubber Band
• Irrationals Exist
• Multiple Choice Probability Puzzle
• Random Eratosthenes
• Wrapping Up Square Dissection
• Dissecting A Square Part 2
• Dissecting A Circle
• Dissecting A Square
• An Oddity In Tennis
• Decision Tree For Tennis
• Decision Trees In Games
• A Matter Of Convention
• Do You Nourish Or Tarnish
• Binary Search Reconsidered
• Two Equals Four
• The Lost Property Office
• The Forgiving User Interface
• Setting Up RSS
• Withdrawing From Hacker News

• Random Writings.
• Colins Blog 2010
• Colins Blog 2009
• Colins Blog 2008
• Colins Blog 2007
• Colins Blog Before 2007

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.

The algorithm

13 x 19 -> 0 6 38 19 3 76 -> 1 152 -> 95 0 304 247 ^^^

So here's the algorithm with an example, shown at right. We start by putting our numbers to be multiplied at the top of two columns. We head the third column with a 0, although we don't always list that explicitly. This third column will be a running total.

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.

A quick check: average of 13 and 19 is 16. 16 squared is 256. 16-13 is 3 3 squared is 9 256 minus 9 is 247 So that's OK.

One final loop through to get 247 in the last column, and that's our answer. If we carry on the left column becomes and remains 0 forever, which is even, so we never add anything into the last column ever again, so once the left column becomes 1, the right column has our answer.

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:

I've been discussing this with some people and I've been intrigued to learn that some highly intelligent people I know are really, really not comfortable with this sequence of equations. And that bothers me, although I know that to some extent I have to accept that it's true. I've made this as simple as possible, making the steps as clear as possible, and yet some clever people are still struggling to follow it in detail. So if you're having trouble following it, don't thing it's because you're stupid, because there are clever people that have trouble with it. You may very well be one of them.

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:

Again, we've used A' for half of A, and B' for the double of B.

So this is still true provided we:

• Add the number in the second column to the running total
• Halve the number in the first column
• Double the number in the second column

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 2¹³. In exponentiation we multiply things together as opposed to adding them, so we generalise the technique by:

• Replace adding with multiplying
• Replace doubling with squaring.
  • In other words, replace "multiply by 2" with "power of 2."

 
 exp   base
 ===   ====
  13      2 ->     1
   6      4        2
   3     16 ->
   1    256 ->    32
   0  65546     8192
                ^^^^

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

def fast_exp(b,e,I=1): # # Compute b^e where e is # a non-negative integer. # We start with a running # product of I, so this # works with numbers and # matrices. # result = I while e > 0: if is_odd(e): result *= b b *= b e = e / 2 return result

And finally the real payoff. We don't need to take powers of numbers. We can use this algorithm to take powers of matrices as well. We start our running product with the identity matrix, and put the matrix whose power we want in the second column. And it just works.

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.

References

To save you the effort of looking it up yourself, here are the searches for the algorithm on-line, and the wikipedia page:

• https://www.google.co.uk/search?q=russian+peasant+multiplication
• https://www.google.co.uk/search?q=Ethiopian+multiplication
• https://www.google.co.uk/search?q=Ancient+Egyptian+multiplication
• http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication

<<<< Prev <<<< FindingPerrinPseudoPrimes Part2

:

>>>> Next >>>> Fast Perrin Test ...

---

You should follow me on twitter

Comments

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.