[Numeracy 605] Re: 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.

Chip Burkitt chip.burkitt at orderingchaos.com
Wed Nov 3 08:14:10 EDT 2010


That's an excellent explanation of the algorithm. Another is to view the
process as binary arithmetic using base-ten numbers. It becomes very
clear if we write the numbers in binary: 18 = 10010 and 35 =100011. If
we multiply using the halving and doubling algorithm, we get:
10010 x 100011
1001 x 1000110
100 x 10001100
10 x 100011000
1 x 1000110000
-----------------------
1001110110 = 512 + 64 + 32 + 16 + 4 + 2 = 630
Applying the standard algorithm to the binary numbers produces the exact
same partial products. The halving and doubling have been replaced with
even simpler actions: shifting bits left or right. This is, as the video
piece on Ethiopian arithmetic acknowledged, the method employed in
computers for multiplying integers. If you read the last digit of the
numbers in the left-hand column from bottom to top, you get the original
multiplier (in this case 10010) again. The strikethroughs represent a 0
in the multiplier.

Chip Burkitt


On 11/2/2010 1:13 PM, Ladnor Geissinger wrote:

> 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

>

>

> ----------------------------------------------------

> The Math& Numeracy Discussion List

> Numeracy at lincs.ed.gov

> To unsubscribe or change your subscription settings, please go to http://lincs.ed.gov/mailman/listinfo/numeracy

> Email delivered to chip.burkitt at orderingchaos.com

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lincs.ed.gov/pipermail/numeracy/attachments/20101103/466195c6/attachment.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: chip_burkitt.vcf
Type: text/x-vcard
Size: 153 bytes
Desc: not available
Url : http://lincs.ed.gov/pipermail/numeracy/attachments/20101103/466195c6/attachment.vcf
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5613 bytes
Desc: S/MIME Cryptographic Signature
Url : http://lincs.ed.gov/pipermail/numeracy/attachments/20101103/466195c6/attachment.bin