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.
Doublethe number in the first column, andhalvethe number in the second column.

- If the number in the second column is
odd, divide it by two anddrop 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 numbersin 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 86~~114 43Keep doubling, halving, and crossing out until the number in the second column is 1.

~~57 86~~114 43 228 21~~456 10~~912 5~~1824 2~~3648 1Add up the remaining numbers in the first column.

~~57 86~~114 43 228 21~~456 10~~912 5~~1824 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 Egyptiansinvented a similar process thousands of years earlier, andcomputers 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, butI 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

I answered (this was probably my first exposure to the method):

Hi, Kara, Russian Peasant Multiplication is actually a way ofsimultaneously 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, wedivide it by two repeatedlyand 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 that10 =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 ispeeling 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 tomultiply 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 to10 * 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 212 12121 0 4 24 018 4848-- 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. Bymarking 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 10~~12 5~~24 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 ismultiply 6 by either a one or a zeroin each place (which is really just selecting whether to include it in the sum), andshift it one place to the lefteach 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 1~~12 2~~24 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. Youdoubledown one column and takehalvesdown the other, dropping remainders, until the halving column reaches 1. Then youcross outthe rows where the halving produced an even number andaddthe 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 1Why 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 astandard 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 isshifted by 1 place, which is equivalent to amultiplication 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, sowhen 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 seehow 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 remainderif 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.

Uncle JimAnother 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. \)

Dave PetersonThanks! 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.