In recently discussing Roman numerals, we ran across Egyptian multiplication. An improvement on that method is called the Russian peasant method, and deserves attention.
How to do it
First, let’s look at the Ask Dr. Math FAQ on the subject:
What is Russian peasant multiplication? How do I use it?
The way most people learn to multiply large numbers looks something like this:
86 x 57 ------ 602 + 4300 ------ 4902If you know your multiplication facts, this “long multiplication” is quick and relatively simple. However, there are many other ways to multiply. One of these methods is often called the Russian peasant algorithm. You don’t need multiplication facts to use the Russian peasant algorithm; you only need to double numbers, cut them in half, and add them up. Here are the rules:
- Write each number at the head of a column.
- Double the number in the first column, and halve the number in the second column.
- If the number in the second column is odd, divide it by two and drop the remainder.
- If the number in the second column is even, cross out that entire row.
- Keep doubling, halving, and crossing out until the number in the second column is 1.
- Add up the remaining numbers in the first column. The total is the product of your original numbers.
You may recognize similarities between this and Egyptian multiplication; there, instead of halving the second factor, we doubled starting with 1, and subtracted to choose rows that add up to the second factor. Both methods make it unnecessary to learn multiplication tables (or even, as we saw last time, to have a place-value number system).
Let’s multiply 57 by 86 as an example:
Write each number at the head of a column.
57 86Double the number in the first column, and halve the number in the second column.
57 86 114 43If the number in the second column is even, cross out that entire row.
57 86114 43Keep doubling, halving, and crossing out until the number in the second column is 1.
57 86114 43 228 21456 10912 51824 23648 1Add up the remaining numbers in the first column.
57 86114 43 228 21456 10912 51824 2+ 3648 1 4902
And there’s the answer, like magic! Of course, it’s not really magic; we’ll look into why it works next.
Real Russian peasants may have tracked their doublings with bowls of pebbles, instead of columns of numbers. (They probably weren’t interested in problems as large as our example, though; four thousand pebbles would be hard to work with!) Russian peasants weren’t the only ones to use this method of multiplication. The ancient Egyptians invented a similar process thousands of years earlier, and computers are still using related methods today.
Computers use essentially this method, but in binary, where doubling and halving both amount to mere digit-shifting. We’ll see what that looks like soon.
Why does it work? It’s all about binary
Good students want to know why it works, not just how to do it. We’ll look at two such questions, so that if one doesn’t quite work for you, the other might. Here is the first, from 1998:
Russian Peasant Method of Multiplication I understand the 'Russian peasant' method of multiplication, but I do not understand why it works. ex:39 x 5278 x 26156 x 13 (double and halve)312 x 6624 x 3 1248 x 1 156 + 624 +1248 = 2028 add only left with odd right Can you explain? Thanks
I answered (this was probably my first exposure to the method):
Hi, Kara, Russian Peasant Multiplication is 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.
What follows is one of several methods of base conversion; we’ll have a series on bases sometime soon.
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
The last line says what it means to say that \(10_{ten}=1010_{two}\): The place values are 8, 4, 2, 1 respectively, so 1010 base 2 means $$1\cdot8+0\cdot4+1\cdot2+0\cdot1=8+2=10.$$
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.
Each division by 2 produces a remainder that is the next binary digit, starting at the right. A computer thinks of this as shifting the number one place to the right, with the last digit shifting into the remainder.
Now we’ve found that we can write 10 as the sum 8 + 2, a sum of powers of two.
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.
Here we’ve doubled the second factor, 6, repeatedly, and added together those which we need based on the binary of the first factor, 10.
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.
So we add the doubles of 6 corresponding to the 1’s in the binary representation for 10. In the table above, the doubling starts on the second line, and we shift that column up in the actual method (next) so that the doubles we use are written on the rows with an odd number in the first column (which produces a 1 in the second column).
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 version of the algorithm is written backward from the usual, due to the order in which we obtained it, and I’ve marked rows to use (*) rather than crossing out the rows to ignore. Using the form we’ve seen, the work looks like this:
6 1012 524 2+ 48 1 60
Now, how do computers do the same thing?
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 shift 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!
I mentioned the Egyptians because this method is just a refinement of Egyptian multiplication. Here’s how that method works for this same problem, \(6\times10\):
6 112 224 4+ 48 8 60
Here, rather than divide 10 by 2 repeatedly in the second column, we multiplied 1 by 2 repeatedly. Then we find a set of those multiples that add to 10, by subtracting from 10: $$10-8=2; 2-2=0\), so \(10=8+2$$ Therefore, we add the corresponding multiples of 6, and get our answer. The Russian peasant amounts to the same thing, but without the need to search for addends. Possibly the reason the Egyptians didn’t do this is that halving was a little less convenient for them with their notation. (I don’t know how actual Russian peasants did this!)
Why again? Another perspective on binary
Here is a similar question from 2003:
How Does This Multiplication Method Work? I've just learned a new way to multiply, where all you have to do is double, split in half, and add. You double down one column and take halves down the other, dropping remainders, until the halving column reaches 1. Then you cross out the rows where the halving produced an even number and add the remaining numbers in the doubling column. For example, to multiply 27 * 38, it would work like this: 27 38 cross out the rows with 38,4,2 since they're even and 54 19 add the numbers left in the doubling column. 108 9 54 + 108 + 864 = 1026 and 27 * 38 = 1026 216 4 432 2 864 1 Why does this work? How could you extend this to division, where all you have to do is double, halve, and add?
Doctor Tom, also new to the method, answered, also seeing the binary connection, but starting with the multiplication rather than the conversion:
Hi Cathy, That's nice! I had not seen this method before. What it amounts to is a standard multiplication, but using base 2. Let me illustrate by showing how a base-2 multiplication of those same two numbers would work: 27 = 11011 (in base 2, 16 + 8 + 2 + 1) 38 = 100110 (32 + 4 + 2)
These could be obtained by the conversion method I demonstrated above.
Now if I do base-2 multiplication just like I'd do it in base-10, here's what it would look like when you multiply just before you add:
11011
100110
------
00000
11011
11011
00000
00000
11011
-------------
Note how simple the multiplications are: 1 times the number is itself, and 0 times the number is 0, so all we’re doing is writing shifted copies of the number. Normally, we would now add all the partial products, giving \(100\ 0000\ 0010_{two}=1026\_{ten}\). But we won’t be adding in binary.
Now if you look at the terms that you need to add up to make the final total, each successive row is shifted by 1 place, which is equivalent to a multiplication by 2. Thus the non-zero rows represent, from top to bottom: 27 x 2 27 x 4 27 x 32 And this makes sense--if you add them together, you obtain 27(2 + 4 + 32) = 27 x 38. Notice that in the left row of the sums in your example, we've got 27, 27x2, 27x4, 27x8, and so on, but we've somehow managed to toss out all the ones that shouldn't be there, leaving only 27x2, 27x4 and 27x32.
There’s just one detail left to understand.
OK, so when do we get non-zero rows? The answer is: whenever there's a "1" in the binary expansion of 38. Let's look at 38 and see how to figure out its binary expansion. The first thing you want to find is if the final digit is 1. That will occur if its final digit is odd. To find the next most significant binary bit, divide by 2, tossing the remainder if necessary, and look at the final digit of that. If it's odd, there will be a 1 in the binary expansion, and so on.
This amounts to our conversion to binary.
When you did successive divisions by 2 to 38 in your example, you got: 38, 19, 9, 4, 2, 1 Look at the odd-even pattern here, where I write 0 for even and 1 for odd: 0, 1, 1, 0, 0, 1 This is just the binary expansion of 38, but in reverse order.
Again, here is the multiplication:
27 38(0) 54 19 (1) 108 9 (1)216 4(0)432 2(0) + 864 1 (1) 1026
The numbers we add, 54, 108, and 864, correspond to the non-zero rows in the binary multiplication we did.
I hope that's enough to make it clear to you why the system works. If not, go though a couple of other examples. Notice that there's nothing special about the 27 side; whatever number you put in that column just keeps doubling up and you just need to select the right ones to make the binary multiplication work. What you need to do is convince yourself that the other side where you successively divide indicates the proper positions for 1 bits in the number that you place in the position occupied by 38 in your example.
Russian division?
He didn’t answer the part about how to extend this to division. The Egyptians had a related way to divide, which we saw last time, but I’ve never heard of a “Russian peasant division”, and I can’t think of a way to use both doubling and halving to do it. So the best answer I could have given would be to demonstrate Egyptian division.
Let’s use Egyptian division to undo the multiplication we just did, namely to divide 1026 by 27:
1 27 2 54 4 108 8 216 16 432 32 864
We’ve doubled starting at 1 and at the divisor, 27, until the next number in the right column would be greater than the dividend, 1026. Now we take the dividend, and repeatedly subtract the largest number less than what we have left:$$1026-{\color{Blue}{864}}=162\\162-{\color{Green}{108}}=54\\54-{\color{Red}{54}}=0$$ We mark the rows we used, and add the numbers in the left column:
1 27 2 54* 2 4 108* 4 8 216 16 432 32 864* 32 38
That’s our quotient.
In this Egyptian method, we had to search for the rows to use; Russian multiplication avoids that step, but I see no way to avoid that (or something similar) for division.
Here is how computers might do the same division, if they simply used long division in binary (they actually use much faster methods that are less useful for humans):
$$1026_{ten}=100\ 0000\ 0010_{two}\\27_{ten}=1\ 1011_{two}$$
and so on
$$\begin{aligned}100\ 0000\ 0010&\\\underline{-11\ 0110\ 0000}&\leftarrow11011\times10\ 0000\\1010\ 0010&\\\underline{-110\ 1100}&\leftarrow11011\times100\\11\ 0110&\\\underline{-11\ 0110}&\leftarrow1\ 1011\times10\\0&\end{aligned}$$
What we did here was to shift the divisor left as far as possible while staying less than the dividend; then subtract and repeat. The first subtraction was shifted left 5 places, so the quotient is 100000; the second subtraction was shifted left 2 places, so the quotient is 100, and the third subtraction was shifted left 1 place, so the quotient is 10. Adding the partial quotients, the quotient is \(10\ 0000+100+10=10\ 0110\); which is 38.
And this amounts to the same subtractions we did in the Egyptian division.
Another way to understand why the “Russian peasant” multiplication algorithm works, without having to think explicitly about binary numerals, is to consider the effect of each step one at a time. For concreteness, I’ll illustrate with your example problem of multiplying 57 (the first factor, or “multiplicand”) by 86 (the second factor, or “multiplier”).
For the first step, since the multiplier 86 is even, we can get an equivalent multiplication problem by halving the multiplier while doubling the multiplicand. Put differently, we can apply the associative law, as follows:
57⨉86 = 57⨉(2⨉43) = (57⨉2)⨉43 = 114⨉43
So we can cross out the original problem, 57⨉86, and write a new, equivalent problem, 114⨉43, underneath it.
For the next step, we cannot proceed in quite the same way, since the new multiplier 43 is odd and we can’t write it as twice an integer. We can, however, write 43 as 1 plus twice an integer, and then apply the distributive law together with the associativity of multiplication, as follows:
114⨉43 = 114⨉(1 + 2⨉21)
= 114⨉1 + 114⨉(2⨉21)
= 114 + (114⨉2)⨉21
= 114 + 228⨉21
So we write a new multiplication problem, 228⨉21, on the next line, but leave the previous multiplicand, 114, not crossed out in the line above, since we will have to add together 114 and the product 228⨉21 in order to get the product 114⨉43.
Continuing in this way, we get a series of multiplication problems with successively smaller multipliers (and larger multiplicands) until we get to a trivial problem where the multiplier is 1. At each step where the multiplier is even, we can double the multiplier and divide the multiplicand exactly in half, getting a new problem with exactly the same product as the previous problem, which we can then cross out. But whenever the current multiplier is odd, we subtract 1 from it before halving, and so we must leave a copy of the current multiplier to be added to the new product in order to get the product for the current problem.
For our example problem 57 ⨉ 86, the full series of equivalent expressions, written in standard mathematical notation would be:
57⨉86
= 114⨉43
= 114 + 228⨉21
= 114 + 228 + 456⨉10
= 114 + 228 + 912⨉5
= 114 + 228 + 912 + 1824⨉2
= 114 + 228 + 912 + 3648⨉1
= 114 + 228 + 912 + 3648
= 4902
Of course the convenient two-column format used in the Russian peasant algorithm saves the trouble of copying a growing list of addends from line to line,
Going from our specific example to the general case, I’ll summarize by saying that the Russian peasant multiplication algorithm works by recursively applying the following identity for positive integers \(n\) and \(m\):
\( n \times m = \left\{ \begin{array}{ll}
n & \mbox{if $m=1$} \\
(2n) \times (m/2) & \mbox{if $m$ is even} \\
n + (2n) \times ((m-1)/2) & \mbox{if $m$ is odd and $m>1$}
\end{array}
\right. \)
Thanks! Our FAQ includes two explanations of the reason for the method, each of which has some resemblance to yours, but was not clear enough in my mind to want to include. Yours definitely deserves inclusion.