Russian Peasant Multiplication

Paul Hunt has let us know about this method of multiplication created by the Russians (Paul Hunt's Hint). 


What a little wonder!


These Russians are realistically creative.


From the Math Forum @ Drexel (Math Forum, Drexel), we read:

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	5
1824	2
3648	1

Add up the remaining numbers in the first column.


57	86
114	43
228	21
456	10
912	5
1824	2
+ 3648	1
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.

Our explanation for such a phenomenon is:

Suppose we are multiplying constant A by constant B.

We then have A x B.

Now suppose the result is C, another constant, so that we now have  A x B = C.

We know that if we multiply A by a constant, say t, and we divide B by the same constant, the result remains unaltered. 

Let's prove that:

At x 1/t B = (t x 1/t) x A x B  = A x B.

If we keep on applying their recipe, we then have always the same result, C, that we had at the beginning of the proposal, when doing A x B.

Notice that if we have even numbers that factor nicely, we simply pick the result to the left and that is already our C:

4    16 

8     8

16   4

32   2

64   1

4 x 16 = 64.

Notice that we can always double the first number with no difficulties but we frequently will have difficulties in halving the second number, since lots of times it will be an odd number.

Notice that any number times two will give us an even number, so that we will always have even numbers to the left, apart from at most the first, at the very top of the column.

If the second number factors nicely we get only even numbers on the second column. In this case, we should be getting the C from the first column, last line in the process.

The process resumes to the following:

a) Even/odd number, even number that perfectly divides by two all the way: We do not strike any and get C from the last line, left.

b) Even/odd number, even number that does not perfectly divide by two all the way/odd number: Strike the even number row, that is the row where there is an even number to the right in the process and add up what is not struck.

The process becomes a bit more complex when we have an odd number or an even number that does not perfectly divide by two all the way to the right side then.

That is obviously because we are halving something that does not split nicely into two (there is a remainder).


In mathematical writing, we could translate what we do to the numbers involved in the Peasant Multiplication in the following way:

Suppose we have  X * Y as our original proposal.

We then do  ((X*2)*2)*2  to the left side by the fourth line of our calculation. Thus, X₃ = ((X*2)*2)*2  and X₀ = X.

(We do |_ |_(|_(Y/2)_| )/2_| )/2_|  to the right side by the fourth line of our calculation. Thus, Y₃ = |_ |_(|_(Y/2)_| )/2_| )/2_|  and Y₀ = Y.

|_(Y/2)_| = (Y-1)/2 if Y = 2n + 1

and

|_(Y/2)_| = Y/2 if Y = 2n

If we do left number times right number, we get  2X_n-1 (Y_n-1-1)/2, that is, X_n-1 (Y_n-1-1), that is, X_n-1 Y_n-1- X_n-1 whenever the right number is not an even number.

This just means that we have to add X_n-1 to recover our original calculation (notice that, when we translate the index, we divide and multiply by two an equal number of times).

When our right result is 1, all we have to do is then adding up all Xs, which are then going to appear only on the lines where we do not have an even number to the right.

This is a really interesting system, right?

___________________________________________

DO YOU WANT TO PLAY LOVE GAMES? GET THE BOOK HERE!

________________________________________________________