Russian Peasant Multiplication:
Fun With Binary
by John C. Darrow
(1986 or earlier)
Folklore has it that, in certain Siberian villages, the peasants have never learned to multiply numbers as we do. However, they have developed a method that uses only doubling, halving, and addition of numbers to accomplish multiplication of two numbers (See Figure 1). The numbers to be multiplied are written side by side, with space below them. One of the numbers (usually the smaller) is successively halved, with fractions dropped, and the results written below it, until the number 1 is reached. The other number is successively doubled, with results written beside the other column of numbers. Any even numbers in the first column are considered "evil" and eliminated along with the corresponding numbers in the other column. The remaining numbers in the second column are added, and the result is invariably the correct answer.
Why does it work? Figure 2 illustrates. The second column contains the second number times successive powers of two (starting with 1, the zeroth power of two), while the process of halving the first number and only keeping the odd results has effectively translated it into binary (a sum of powers of two.) Adding the numbers in the second column adds the second number times each of the appropriate powers of two to give the correct answer.
Figure 1
An example: 29 * 47
A 
B 
Successively halved 
Successively doubled 
29 
47 
14 
94 
7 
188 
3 
376 
1 
752 
Now, since 14 in Column A is even, it is eliminated, along with its partner 94. The remaining numbers in Column B are added.
A 
B 
Successively halved 
Successively doubled 
29 
47 
Xxxxx(14) 
Xxxxx(94) 
7 
188 
3 
376 
1 
752 
 

Total 
1363 
The result, 1363, is the correct answer to 29 times 47.
Figure 2
Why It Works
A 
B 
C 
D 
Successively halved 
Successively doubled 
Remainder of Column B 
Column A / 2 equivalent 
29 
47 
1 
47 * 1 
Xxxxx(14) 
Xxxxx(94) 
0 
47 * 2 
7 
188 
1 
47 * 4 
3 
376 
1 
47 * 8 
1 
752 
1 
47 * 16 
 

Total 
1363 
Reading Column C up yields 11101, the binary equivalent of 29 (16 + 8 + 4 + 0 + 1). When 94 is eliminated, and the other numbers from Column B added, we can use the equivalents from Column D to see we have:
(47 * 16) + (47 * 8) + (47 * 4) + (47 * 1)
Rearranging, we have:
47 * (16 + 8 + 4 + 1)
or:
47 * 29