Russian peasant multiplication

Apparently Russian peasants used an interesting alternate algorithm for multiplication.

The algorithm is quite simple.

1. Write the two numbers that you are multiplying side by side.

2. Create a column under the number on the right. Each entry should be half of the entry above it, ignoring any fractional amounts (example: if the number 5 is the right column, the number below it should be 2), stopping when the number 1 appears.

3. Create a column under the number on the left. Each entry should be twice the entry above it. Stop when the left column has the same number of entries as the right column.

4. Cross out any number in the left column whose corresponding number in the right column is even.

5. Add the numbers in the left column which are not crossed out.

The number you find in step 5 is the product of the two numbers you started with!

Example:

 32  25
 64  12
128   6
256   3
512   1
-------
800

So 32 x 25 = 800.

As liveforever pointed out to me, this method is of course commutative.

How it Works

What the algorithm described above does is in fact convert one of the two numbers into binary (the number which is halved on every line) and then do the required calculation.

To explain a little better let's take the example 13*9 and let the 13 be the number which we are going to halve. The table we end up with will look like this:

13      9
 6     18
 3     36
 1     72
      ---
      117

Now let's look at a different way of doing the same calculation by converting the "13" into binary.

In binary 13=1101=(1*8)+(1*4)+(0*2)+(1*1)

So to multiply 13 by 9 we could work out the following:

({9*1}*8)+({9*1}*4)+({9*0}*2)+({9*1}*1)

Since we're using binary we're dealing with a lot of 1s and 0s and they are all conveniently irrelevant so the above calculation can be written:

(9*8)+(9*4)+(9*1)

One way to convert a number in base 10 into binary is through the following procedure:

1. Take the number you wish to convert. If that number is odd you will get a "1" as the rightmost digit of the binary number if it is even you will get a "0".
2. Then halve the number. If you end up with a remainder of one you discard it because you have already accounted for that remainder by putting a "1" in the previous column.
3. If the result (the halved number with any remainder discarded) is odd put a "1" in the column to the left of the previous digit, if it is even put in a "0".
4. Repeat the process until you reach one.

So for 13 you get a "1" - it's odd. Then a "0" -6 is even. Then a "1" - 3 is odd. Then a "1" - 1 is odd. (If you continue you get infinite zeroes).

So for 13 you get 1011 but this procedure generates values starting from the rightmost column so 1011 should be read as 1101.

Now let's look again at the table and add a few columns.

13    1     9    (9*1)
6     0    18    (9*2)
3     1    36    (9*4)
1     1    72    (9*8)

Now to find the solution all you need to do is multiply the values in the second column by those in the third column and add up all those values. All the Russian peasant system does is miss out the second column (and the fourth) and then cross out all rows that have even numbers in their first column because these would have Os in my second column so they would not affect the final solution.