Russian Peasant Method of MultiplicationDate: 10/07/98 at 20:46:39 From: Kara Brown Subject: 'Russian peasant 'method of multiplication I understand the 'Russian peasant' method of multiplication, but I do not understand why it works. ex: 39 x 52 78 x 26 156 x 13 (double and halve) 312 x 6 624 x 3 1248 x 1 156 + 624 +1248 = 2028 add only left with odd right Can you explain? Thanks Date: 10/08/98 at 09:06:46 From: Doctor Peterson Subject: Re: 'Russian peasant 'method of multiplication Hi, Kara, Here's a past answer in our archives describing Russian Peasant Multiplication: http://mathforum.org/dr.math/problems/nickless8.19.97.html It's actually a way of simultaneously converting a number to binary and multiplying it by another number. To show the relation clearly, I'll work with a small example, 10 x 6. I'm going to assume that you have at least some knowledge of binary numbers; if not, write back and I can rephrase this more simply. To convert the number 10 to binary, we divide it by two repeatedly and note which divisions give a remainder (of 1): 10 / 2 = 5 r 0 ------------------------------> 0 5 / 2 = 2 r 1 ----------------------> 1 2 / 2 = 1 r 0 --------------> 0 1 / 2 = 0 r 1 ------> 1 The answer is 10 = 1010 in binary (reading the remainders upwards). This means that 10 = 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 = 2^3 + 2^1 = 8 + 2 To see why this works, just write everything (except the 2) in binary: 1010 / 2 = 101 r 0 --------------------------> 0 101 / 2 = 10 r 1 -----------------> 1 10 / 2 = 1 r 0 ---------> 0 1 / 2 = 0 r 1 -> 1 All we're really doing is peeling off the rightmost digit at each step. Now to multiply 10 by any other number, we just have to use the distributive rule to multiply that number by each power of 2 that is present in 10: 10 * x = (8+2) * x = (2^3 + 2^1) * x = 2^3 * x + 2^1 * x We can find these multiples of powers of two by starting with the given number and doubling it repeatedly: 2^0 * 6: 6 2^1 * 6: 6 * 2 = 12 2^2 * 6: 12 * 2 = 24 2^3 * 6: 24 * 2 = 48 The answer to 10 * 6, then, is (2^3 * 6) + (2^1 * 6) = 48 + 12 = 60. Now we can put everything together in one little chart: Divide by 2 Remainder Power of 2 Double Sum ----------- --------- ---------- ------ ------- 10 5 0 1 6 2 1 2 12 12 1 0 4 24 0 1 8 48 48 -- 60 The two leftmost columns find the binary digits for 10, the next two find 6 multiplied by powers of two, and the last column sums the powers of two that form 10, multiplied by 6, to get the result. Russian multiplication just compresses the first, fourth, and fifth columns into a simple format: 10 6 5 12* 2 24 1 48* --- 60 You don't need to write down the remainder, because it's 1 if the number you just divided by 2 is odd. You don't need to write down the powers of two, just the doublings. By marking the doublings that correspond to odd halvings, you select the terms to add to get the result. You may also notice that the lines that were added (marked by asterisks) show the binary value 1010 when you read up. This also corresponds to how binary numbers are multiplied, because all we do is multiply 6 by either a one or a zero in each place (which is really just selecting whether to include it in the sum), and shifting it one place to the left each time (which is really a doubling): 0110 6 x 1010 x 10 ------ ----- 0000 (6 * 1) 0110 6 * 2 0000 (6 * 4) 0110 6 * 8 ------- ----- 0111100 6 * 10 I hope that makes it all clear. It's amazing how ancient people (including the Egyptians) multiplied the same way computers do today! - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/