[Numeracy 604] Russian peasant multiplication

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