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 zero-th 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