Why does the peasant algorithm work

Dividing 85 by 2 and dropping the remainder we get successively: 85, 42, 21, 10, 5, 2, 1. Now, multiply by 2 the second number, 18, as many times: 18, 36, 72, , , , Let's write these in two columns:. I listed the numbers in two colors for an important reason. We have to look at the first column and mark there the odd numbers. These appear in red. The even numbers are orange - diluted red - to signify their lack of importance for the next step. On the next step, mark the numbers in the second column that are in the same rows with the odd numbers in the first.

These are also in red. For the convenience sake, I added a third column where the red numbers from the second one have been separated:. All that remains at this stage is to add up all the numbers in the third column. As you can see, the result is the same, but is obtained in fewer steps.

This is true in general: if tasked with applying the algorithm to finding the product of two numbers a and b, make the smaller number first, the larger one second. Now, let's see why the algorithm works. Since halving and doubling play such an important role in the algorithm, it should not come as a great surprise that its real foundation lies in the binary system. To obtain the binary representation of a number, the number is to be repeatedly divided by two, the remainders recorded and then written in the reverse order.

Check now the "Show binary" box:. We see two additional columns: the first indicates the step and a power of 2 , the second contains the binary digits of 85 written from the bottom upwards:. Note that a binary digit is the remainder of division by 2: it is 1 for odd numbers and 0 for even numbers.

Next, cross out the rows in which the number on the left is even. Extend your line to cross out the corresponding number on the right as well. Find the sum of the remaining numbers in the right column. The sum of these numbers is equal to the product you would get from multiplying the original numbers using the standard method.

The Russian peasant multiplication method works because it converts the problem into binary base 2 multiplication, rather than base It does this by halving and doubling the numbers you are trying to multiply since halving and doubling convert all numbers into multiples of 2, or into factors of numbers that are divisible by 2. Ask your students why we had to add the two numbers 72 and When we halved 37 we ignored the one to make the number even in order to divide it.

It's easy to see why this works, because as you move down both columns simultaneously, the product of the numbers in the two columns is always the same. Looking at the top entries, this product is clearly times x. Looking at the bottom entry gives you the product. But suppose you want to multiply by a number which is not a power of 2. Say I want to multiply x by Then I go through the same process, except that when you divide the numbers in the left-hand column by 2, just ignore the remainder in case the number is odd.

Now to obtain the final answer I need to add x to the number at the bottom of the right-hand column. In this case, as we move down the two columns, the product at the second step is no longer the same as the product at the first, because 17 became 8, which is not actually half of In general, if you're multiplying x by a and go through this process, every time the number in the left-hand column is odd, the product of the two columns one line down will be smaller than the product before.

To compensate, you need to add in the number which is in the right-hand column at this stage when you get to the end. Cross out all the rows where the left-hand column is even, but save the rest. Now add up all the entries in the right-hand column which are not crossed out and you'll have your answer. This file is also available in postscript, dvi, and idvi formats. Look at www. Here's my own attempt to explain it: [Please use a non-proportional font so the columns line up. The procedure is described in Jan Gullberg's "Mathematics" and other sources.