Russian Peasant Method of Multiplication

Date: 10/07/98 at 20:46:39
From: Kara Brown
Subject: 'Russian peasant 'method of multiplication

I understand the 'Russian peasant' method of multiplication, but I do 
not understand why it works.

ex:        39 x 52
           78 x 26
          156 x 13   (double and halve)
          312 x 6
          624 x 3
         1248 x 1

      156 + 624 +1248  =  2028   add only left  with odd right

Can you explain?  Thanks

Date: 10/08/98 at 09:06:46
From: Doctor Peterson
Subject: Re: 'Russian peasant 'method of multiplication

Hi, Kara,

Here's a past answer in our archives describing Russian Peasant 
Multiplication:

 http://mathforum.org/dr.math/problems/nickless8.19.97.html   

It's actually a way of simultaneously converting a number to binary 
and multiplying it by another number. To show the relation clearly, 
I'll work with a small example, 10 x 6. I'm going to assume that you 
have at least some knowledge of binary numbers; if not, write back and 
I can rephrase this more simply.

To convert the number 10 to binary, we divide it by two repeatedly and 
note which divisions give a remainder (of 1):

    10 / 2 = 5 r 0 ------------------------------> 0

             5 / 2 = 2 r 1 ----------------------> 1

                     2 / 2 = 1 r 0 --------------> 0

                             1 / 2 = 0 r 1 ------> 1

The answer is 10 = 1010 in binary (reading the remainders upwards). 
This means that

    10 = 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 = 2^3 + 2^1 = 8 + 2

To see why this works, just write everything (except the 2) in binary:

    1010 / 2 = 101 r 0 --------------------------> 0

               101 / 2 = 10 r 1 -----------------> 1

                         10 / 2 = 1 r 0 ---------> 0

                                  1 / 2 = 0 r 1 -> 1

All we're really doing is peeling off the rightmost digit at each 
step.

Now to multiply 10 by any other number, we just have to use the 
distributive rule to multiply that number by each power of 2 that is 
present in 10:

    10 * x = (8+2) * x = (2^3 + 2^1) * x = 2^3 * x + 2^1 * x

We can find these multiples of powers of two by starting with the 
given number and doubling it repeatedly:

    2^0 * 6: 6

    2^1 * 6: 6 * 2 = 12

    2^2 * 6:         12 * 2 = 24

    2^3 * 6:                  24 * 2 = 48

The answer to 10 * 6, then, is (2^3 * 6) + (2^1 * 6) = 48 + 12 = 60.

Now we can put everything together in one little chart:

    Divide by 2  Remainder  Power of 2  Double    Sum
    -----------  ---------  ----------  ------  -------
        10
         5           0          1          6
         2           1          2         12       12
         1           0          4         24
         0           1          8         48       48
                                                   --
                                                   60

The two leftmost columns find the binary digits for 10, the next two 
find 6 multiplied by powers of two, and the last column sums the 
powers of two that form 10, multiplied by 6, to get the result.

Russian multiplication just compresses the first, fourth, and fifth 
columns into a simple format:

    10      6
     5     12*
     2     24
     1     48*
           ---
           60

You don't need to write down the remainder, because it's 1 if the 
number you just divided by 2 is odd. You don't need to write down the 
powers of two, just the doublings. By marking the doublings that 
correspond to odd halvings, you select the terms to add to get the 
result. You may also notice that the lines that were added (marked by 
asterisks) show the binary value 1010 when you read up.

This also corresponds to how binary numbers are multiplied, because 
all we do is multiply 6 by either a one or a zero in each place (which 
is really just selecting whether to include it in the sum), and 
shifting it one place to the left each time (which is really a 
doubling):

       0110       6
     x 1010    x 10
     ------   -----
       0000  (6 * 1)
      0110    6 * 2
     0000    (6 * 4)
    0110      6 * 8
    -------   -----
    0111100   6 * 10

I hope that makes it all clear. It's amazing how ancient people 
(including the Egyptians) multiplied the same way computers do today!

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/