Russian Peasant Multiplication: how does it work?
Kevin Fortin
Hello,
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
works.
The earlier Egyptian method was easy to understand, but not this (at
least for me).
Thanks,
Kevin
Lee Lady
In article <34FAEB...@ufl.edu>, Kevin Fortin <kfo...@ufl.edu> wrote:
>Hello,
>
>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
>works.
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.)
If you want a longer explanation, with several examples, look at
"Bride of the Lazy Man" at
<Http://www.math.Hawaii.Edu/~lee/elementary/Lazy2.pdf>. (This file is
also available in postscript, dvi, and idvi formats. Look at
www.math.Hawaii.Edu/~lee/elementary/ and click on the format you prefer.)
--
Trying to understand learning by studying schooling
is rather like trying to understand sexuality by studying bordellos.
-- Mary Catherine Bateson, Peripheral Visions
la...@Hawaii.Edu <http://www2.Hawaii.Edu/~lady/ >
Kevin Fortin
Thanks to the sci.math readers whose responses helped me to understand
"Russian Peasant Multiplication"!
Here's my own attempt to explain it:
[Please use a non-proportional font so the columns line up. Also, I
will use the caret (^) to indicate an exponent, e.g. 2^3 = "two cubed".
The procedure is described in Jan Gullberg's "Mathematics" (1997) and
other sources.]
Example: 19 x 54 = X
(H = "halving column", D = "doubling column"; in column H, any remainder
is discarded after each halving.)
_H_ _D_
54 19 (ignored)
27 38
13 76
6 152 (ignored)
3 304
1 608
The even numbers in column H are crossed out, along with the
corresponding entries in column D across the way. The remaining numbers
in column D are added up to give the product:
19 x 54 = (38 + 76 + 304 + 608) = 1026
After the halving is finished (i.e., you have reached a result of 1),
what matters in column H is whether the numbers are even or odd. The
pattern of even and odd numbers in column H corresponds to a binary (or
base 2) representation of the original number:
Place in
binary
notation
54 even 0 (2^0)
27 odd 1 (2^1)
13 odd 1 (2^2)
6 even 0 (2^3)
3 odd 1 (2^4)
1 odd 1 (2^5)
54 base ten, converted to base 2, equals 110110, or (back in base 10):
(2^5 + 2^4 + 2^2 + 2^1) = (32 + 16 + 4 + 2) = 54. [If the first entry
in column H is even, there will always be a zero in the unit (2^0) place
of the binary representation; if the first entry is odd, there will be a
one in the unit place.]
Therefore, 19 x 54 = 19(2^5 + 2^4 + 2^2 + 2^1) = (608 + 304 + 76 + 38) =
1026.
As 2^0 and 2^3 are not part of the sum shown above that produces 54, the
corresponding products in column D (19 x 2^0 and 19 x 2^3) are also
ignored. The surviving elements of column D are added up to give the
product of 54 x 19.
Hoping this helps others puzzled (as I was) by this method of
multiplying,
Kevin
Lee Lady
This article is essentially a duplication. However using your example, I
can now make my previous explanation even simpler.
In article <34FCB257...@ufl.edu>, Kevin Fortin <kfo...@ufl.edu> wrote:
>Thanks to the sci.math readers whose responses helped me to understand
>"Russian Peasant Multiplication"!
>
>Here's my own attempt to explain it:
>
>[Please use a non-proportional font so the columns line up. Also, I
>SNIP<
>Example: 19 x 54 = X
>
>(H = "halving column", D = "doubling column"; in column H, any remainder
>is discarded after each halving.)
>
>_H_ _D_
>54 19 (ignored)
>27 38
>13 76
> 6 152 (ignored)
> 3 304
> 1 608
>
>The even numbers in column H are crossed out, along with the
>corresponding entries in column D across the way. The remaining numbers
>in column D are added up to give the product:
>19 x 54 = (38 + 76 + 304 + 608) = 1026
Now, as I explained in my previous article, all you need to do to explain
this is notice that when the left-hand column is even, the product of the
two columns remains the same when you move down to the next line.
(For instance, 54 * 19 = 27 * 38.) However when the left-hand column is
odd, this is not quite correct. The discrepancy is in fact the number in
the right-hand column. (For instance, 27 * 38 = 13 * 76 + 38.)
Now if you take the final entry in the right-hand column and add to it
all the discrepancies, i.e. all the other entries in the right-hand
column which appear next to odd numbers in the left hand column, you
recover the original (unknown) product. (As you indicate, 54 * 19 =
608 + 304 + 76 + 38. The point is that 54 * 19 = 27 * 38 =
13 * 76 + 38 = 6 * 152 + 76 + 38 = 3 * 304 + 76 + 38 =
= 1 * 608 + 304 + 76 + 38. )
In my opinion, bringing binary numbers into the explanation just makes it
more confusing.
See <Http://www.math.Hawaii.Edu/~lee/elementary/Lazy2.pdf> ("Bride of
the Lazy Man").