Russian
Peasant
Multiplication

     How would you like to throw away all those hard "times tables" and still be able to multpliy any two numbers? Well, have I got news for you! It's possible. No, really. I'm not joking; nor am I saying "just go punch some calculator buttons" either. Real paper-and-pencil stuff. Only one thing you gotta know: your "2 times tables". Or to be even more specific: know how to double a number (which means "multiply by 2) and cut a number "in half" (which just means "divide by 2").

     But, that's all. If you can do these two simple things, and of course, can add numbers, you're "in business". The name of the process, as you have undoubtedly guessed, is Russian Peasant Multiplication, a method quite common down through the centuries.

     Here's how it works for the numbers 22 × 35. You begin by writing the numbers side-by-side. 


22	 35
     Then you start "halving" one number while at the same time you "double" the other. Our first results are these: 

22	 35
11	 70
     We continue the process until the column in which we are halving reaches the number 1. Also, one other little thing must be observed: when we take the half of an odd number, there is naturally a "remainder of 1"; so we just discard it, throw it away, toss it in the ol' trash basket. And go on with our process as if nothing important had happened. Just such a need arises on our next step in our problem, with 11, then again with the 5. 

22	 35
11	 70
 5	140
 2	280
 1	560
     Now, if you have studied the Egyptian method of multiplication on another page in this website, you might assume that here again we will select certain numbers from the second column to add, the result of which will be our desired product. That's right, but which ones are they? The answer: the ones that are opposite odd numbers on the left!! 

22	 35
11	 70
 5	140
 2	280
 1	560
     So 70 + 140 + 560 = 770, which is the correct product. (Now that wasn't so hard, was it?)

     If we use the Commutative Property of Multiplication, we can work it "the other way around", to compare and check results. 


35	 22
17	 44
 8	 88
 4	176
 2	352
 1	704
     And again 770 is our product, by adding 22, 44, and 704.

Analysis

     Which way was better with this problem: 22 × 35 or 35 × 22? The first time, with the smaller number on the left ("halving") side, definitely required fewer lines of writing. But both ways left us with only three numbers to add. So perhaps in this case, there wasn't too much of a difference either way we go. But it would seem to be good advice in general to use the smaller factor as the one to cut in half. There would be fewer lines of halving-&-doubling in the long run.

     Perhaps you are wondering why this strange process works. Here is part of an explanation. Note: 


22	 35	(1 group of 35)
 11	  70	 (2 groups of 35)
  5	 140	 (4 groups of 35)
  2	 280	 (8 groups of 35)
   1	  560	  (16 groups of 35)
     The parentheses that contain a blue number correspond to the numbers that were added to give the product, which in their turn were chosen because they were opposite an odd number in the first column. And they just happen to add up to 22, the other factor in our problem!

     So now we can say: (2 × 35) + (4 × 35) + (16 × 35) = (2 + 4 + 16) × 35 = 22 × 35 = 770

     Try some more instances of this marvelous procedure and you will soon be convinced of an interesting and historical aspect of mathematics.

Feedback (8/3/02)

We received the following email from Poul Wulff Pedersen, from Denmark, who wishes to add some relevant information to this topic. He wrote:

I saw it many years ago in a Schaum Outline book about Numerical Analysis - and have wondered since if any russian peasant has ever used it. But it seems to have been known in other cultures as well.

Unfortunately I don't understand your "part of an explanation" - but actually it is quite simple: If you compute 22 (in your example) in binary form you get

22 = 10110 = 24 + 22 + 21

Thus

22*35 = (24 + 22 + 21)*35 = 560 + 140 + 70

which are just the multiplies [sic.] picked out by the algorithm.

Another algorithm for multiplication is

a*b = (1/4)*((a + b)2 - (a - b)2)

where the multiplication is replaced by two squares. Squares are easy in binary and - more important - if you use table-look-up for speed you need only a one-dimensional table for squares instead of the two-dimensional multiplication of our school days (a long time ago !). The 1/4 can (with a little skill) be absorbed in the two squares so that you only need the same number of bits for a+b as for a and b. [WTM note: see Multiplication with Squares in this website.]

A third trick in binary is the Booth algorithm which replaces a string of ones by one 1 and a (-1),

11111 = 10000[-1]

so that the additions and shifts corresponding to 11111 is replaced by a shift and one subtraction. The "anti-Booth" is useful for binary subtraction by hand.

To learn more about this topic, click HERE.

Comments?
Send e-mail.		Back to
top		Go back to
Home Page		Go back to
Contents