Subject: Re: Russian Peasant Multiplication: how does it work?
In article <34FAEB0F.C90@ufl.edu>, Kevin Fortin <firstname.lastname@example.org> wrote:
>Could someone point me toward a good explanation of how "Russian Peasant
>Multiplication" works? I saw the method in Jan Gullberg's recent book
>"Mathematics: From the Birth of Numbers", but I still can't grasp why it
This is really easy to understand on the basis of common sense.
Unfortunately, most math books try to give a clever explanation based on
the binary representation of numbers. This works, but the explanation is
harder to follow.
Okay, suppose you want to multiply x by 16. Since 16 = 2^4,
what you should do is to double x 4 times. Now for a larger number,
you might not know quickly what the right exponent is. Say take 512,
which is a power of 2, but you've forgotten which power. But just write
down 512 and write down x. Now divide 512 by 2, getting 256, and at the
same time double x. Keep dividing the left-hand column (the one that
starts with 512) by 2 and doubling the numbers in the right-hand column
(which started with x), until you've reduced the left-hand column to 1.
The number at the bottom of the right-hand column is the product you're
seeking. 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 512
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 17. 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 17.
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.)