[Numeracy 604] Russian peasant multiplication

Archived Content Disclaimer

This page contains archived content from a LINCS email discussion list that closed in 2012. This content is not updated as part of LINCS’ ongoing website maintenance, and hyperlinks may be broken.

Ladnor Geissinger ladnor at email.unc.edu
Tue Nov 2 14:13:49 EDT 2010


The divide by 2, multiply by 2, etc algorithm that has been commented on
lately is often called Russian peasant multiplication. Why it works
seems a bit mysterious only because, as is common in frequently used
algorithms, it has been abbreviated just a bit too much -- everything
that seemed unnecessary has been deleted to cut down on the amount of
writing. Just put the lost little bit back in and itall becomes clear.
Think of it as making _three_ columns of numbers, or a column of
triples. We want to find the product p of b and c (b and c are
explicit natural numbers, p is to be calculated):
First write
b , c , 0 ---------------------------This is our first
triple of numbers, and here b*c + 0 = p.
Now divide b by 2 and multiply c by 2. One of the following cases applies.
Case 1, b = 2*k , then k*(2*c) + 0 = p, so write down the second
triple of numbers
k , 2*c , 0
OR Case 2, b = 2*k +1, then k*(2*c) + c = p, so write down the second
triple of numbers
k , 2*c , c + 0
We are going to do almost the same thing at each of the following steps
of the algorithm.
So suppose that we have already gotten a triple d, e, s for
which d*e + s = p --- this is the loop invariant.
d , e , s
If d = 2*m , then write for the next triple
m , 2*e , s ------------------------ and note that we still
have m*(2*e) + s = p
If on the other hand d = 2*m +1, then write for the next triple
m , 2*e , e+s ----------------------- and note that we still
have m*(2*e) +(e+s) = p

Now you can repeat this process again to get the next triple.
But note that if d = 1 above, then we already have 1*e + s = p , so the
last sum e+s is the explicit number p that we wanted.
Quit.

Notice that instead of waiting until the end to add up some terms in the
second column as in the standard version of this algorithm, we have
simply accumulated the sum as we go along.

Example: 35*18 = p
35 , 18 , 0-----------35*18 + 0 = p
17 , 36 , 1 8-----------17 *36 +18 = p
8 , 72 , 54------------8*72 +(36+18) = p
4 , 144 , 54------------4*144 + 54 = p
2 , 288 , 54------------2*288 +54 = p
1 , 576 , 54------------1*576 + 54 = 630 = p

--

Ladnor Geissinger, Emer. Prof. Mathematics
Univ. of North Carolina, Chapel Hill NC 27599 USA

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lincs.ed.gov/pipermail/numeracy/attachments/20101102/38aae4a1/attachment.html