Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math: FAQ

  Russian Peasant Multiplication  

_____________________________________________
Dr. Math FAQ || Classic Problems || Formulas || Search Dr. Math || Dr. Math Home
_____________________________________________

[ Back to Multiplication Facts ]

Rules
What is Russian peasant multiplication? How do I use it?
Reasons
Why does Russian peasant multiplication work?
Connections
How is the Russian peasant algorithm related to binary numbers?

Back to top

What is Russian peasant multiplication? How do I use it?

The way most people learn to multiply large numbers looks something like this:

        86
      x 57
     ------
       602
    + 4300
     ------
      4902

If you know your multiplication facts, this "long multiplication" is quick and relatively simple. However, there are many other ways to multiply. One of these methods is often called the Russian peasant algorithm. You don't need multiplication facts to use the Russian peasant algorithm; you only need to double numbers, cut them in half, and add them up. Here are the rules:

  • Write each number at the head of a column.
  • Double the number in the first column, and halve the number in the second column.
       If the number in the second column is odd, divide it by two and drop the remainder.
  • If the number in the second column is even, cross out that entire row.
  • Keep doubling, halving, and crossing out until the number in the second column is 1.
  • Add up the remaining numbers in the first column. The total is the product of your original numbers.

Let's multiply 57 by 86 as an example:

    Write each number at the head of a column.

     57   86 

    Double the number in the first column, and halve the number in the second column.

     57   86 
    114  43 

    If the number in the second column is even, cross out that entire row.

     57   86 
    114  43 

    Keep doubling, halving, and crossing out until the number in the second column is 1.

     57   86 
    114  43 
    228  21 
     456   10 
    912 
     1824   2 
    3648 

    Add up the remaining numbers in the first column.

     57   86 
    114  43 
    228  21 
     456   10 
    912 
     1824   2 
    + 3648 
    4902 

Real Russian peasants may have tracked their doublings with bowls of pebbles, instead of columns of numbers. (They probably weren't interested in problems as large as our example, though; four thousand pebbles would be hard to work with!) Russian peasants weren't the only ones to use this method of multiplication. The ancient Egyptians invented a similar process thousands of years earlier, and computers are still using related methods today.



Back to top

Why does Russian peasant multiplication work?

Let's calculate 9 * 8 as an example:

     9   8 
     18   4 
     36   2 
    72 

72 is the only remaining number in the left-hand column, so our answer is 72. Notice that we were multiplying by 2 on one side, and by 1/2 on the other side. 2 * 1/2 = 1, so the overall product did not change:

9 * 8
= 18 * 4
= 36 * 2
= 72 * 1.

We were grouping numbers in a different way, not changing the answer.

If we multiply 8 * 9, we should get the same answer. Can we explain our answer the same way?

     16   4 
     32   2 
    + 64 
    72 

When we cut 9 in half, we dropped the remainder because 9 is an odd number. Because we have "lost" a one, the product of each row should be smaller from now on. Let's find the difference between the first row and the second row:

    8*9 - 16*4
    = 72 - 64
    = 8.

We can rewrite the subtraction as a sum:

    8 * 9
    = 16 * 4 + 8.

Because our product has decreased by 8, we have to add 8 back in again at the end. We can think of the addition as restoring 1 group of 8, for the remainder of 1 that we dropped earlier. In a different problem, we might have to restore several different groups of numbers.



Back to top

How is Russian peasant multiplication related to binary numbers?

Binary numbers are numbers written in base two instead of base ten. This means that place value depends on powers of two instead of powers of ten: instead of ones, tens, and hundreds places, base two has a ones place, a twos place, a fours place, and so on. For example, fourteen in base two is 1110:

    1110 (base 2)
    = 1 * 23 + 1 * 22 + 1 * 21 + 0 * 20
    = 8 + 4 + 2 + 0
    = 14.

Russian peasant multiplication is actually a quick way to convert two numbers to binary form, multiply them together, and convert back to our number system. The connection is not surprising, because binary numbers use base two, and Russian peasant multiplication depends on multiplying and dividing by two. To see the connection more clearly, let's investigate the problem 12*13.

Halving

You can convert a number to binary form by repeatedly dividing by two and keeping track of the remainders. Let's try 12:

    12/2 = 6 remainder 0
    6/2 = 3 remainder 0
    3/2 = 1 remainder 1
    1/2 = 0 remainder 1.

Reading the remainders from bottom to top, we get 1100, so 12 in base two is 1100.

Why does this conversion method work? Let's try cutting twelve in half again, the same way. This time, we'll write everything in base two. (Naturally, 2 in base two is 10.)

    1100/10 = 110 remainder 0
    110/10 = 11 remainder 0
    11/10 = 1 remainder 1
    1/10 = 0 remainder 1.

Dividing by two and then taking the remainder gives us a number's last digit in binary notation.

Here's what we know about 12, so far:

    12 = 1100 (base 2)
    = 1*23 + 1*22 + 0*2 + 0*1
    = 23 + 22
    = 8 + 4.

By halving 12 repeatedly, we have broken it down into powers of two.

The Distributive Property

We are trying to multiply 12 by 13. One way to do this would be to use long multiplication:

       13
     * 12
     ----
       26
    + 130
    -----
      156

Notice that we are adding 2*13 and 10*13 to get our final answer. This works because of the distributive property:

    12 * 13
    = (2 + 10) * 13
    = 2*13 + 10*13.

Of course, we can break 12 down any way we like, and still get the right answer. Let's use our previous work to split the problem into powers of two:

    12 * 13
    = (4 + 8) * 13
    = (22 + 23) * 13
    = 22 * 13 + 23 * 13.

If we can multiply 13 by 2^2 and 2^3, we will be finished.

Doubling

Repeatedly doubling a number multiplies it by powers of two. Let's try doubling 13:

    Number Multiplications so far Power of 2
    13 13 20
    26 13*2 21
    52 13*2*2 22
    104 13*2*2*2 23

Our chart tells us that 22 * 13 + 23 * 13 = 52 + 104 = 156, so 12 * 13 = 156, and we are done.

Putting It All Together

We just used repeated halving and doubling to convert 12 to binary form, then multiply it by 13. Russian peasant multiplication does the same thing, but because it leaves out several steps, the process is much faster. Let's combine our doubling and halving steps to compare the two methods.

    Number
    doubled
    Multiplications
    so far
    Power
    of 2
    Number
    halved
    Division
    Problem
    Remainder
     13  13 20  12  12/2 = 6 0
     26  13*2 21  6  6/2 = 3 0
    52 13*2*2 22 3 3/2 = 1 1
    104 13*2*2*2 23 1 1/2 = 0 1

The columns used in Russian peasant multiplication are highlighted. Notice that when the number in the remainder column is 0, the corresponding row for Russian peasant multiplication is crossed out.


Back to top

- Ursula Whitcher, for the Math Forum

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. Math ®
© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.