Russian Peasant Multiplication
Created | Updated Jun 15, 2007
No, it's nothing to do with the Soviet population explosion, Russian Peasant Multiplication is a method for multiplying two numbers together. It requires only the ability to double or halve a number, and the ability to add up, so you don't need to be good at times tables.
Go Forth and Multiply
Here's an example which multiplies the numbers 57 and 23 together, but the method will work with any numbers, of course:
At the top of a piece of paper, write the first number (57) on the left, and the second number (23) on the right. Mathematicians call these numbers the multiplicand and the multiplier: maybe they should get out more.
Halve the first number and write the result below it. Ignore any fractions, so 57 halved is 28.
Double the second number and write the result below it, so 23 doubled is 46.
Repeat steps 2 and 3 until the left-hand number has reduced to 1. 28 halves to 14, 46 doubles to 92, and so on. Eventually we have 1 in the left-hand column and 736 on the right.
Cross out all the rows where the left-hand number is even, so we will cross out the rows 28/46 and 14/92 here.
Add up all the numbers remaining in the right hand column, for the result. We get 23 + 184 + 368 + 736 = 1,311, so 57 x 23 = 1,311.
| 57 | 23 |
| 28 | 46 |
| 14 | 92 |
| 7 | 184 |
| 3 | 368 |
| 1 | 736 |
| 57 | 23 |
| --- | --- |
| --- | --- |
| 7 | 184 |
| 3 | 368 |
| 1 | 736 |
| Total: | 1,311 |
What's the Secret?
Clever, isn't it? It works by considering the number on the left as a sum of its binary coefficients (powers of two to you and me). 57 can be written as = 1 + 8 + 16 + 32. If you want 57 lots of 23, then we add together one 23 (=23), eight 23s (=184), 16 23s (=368) and 32 23s (=736). Note that we don't need a 2 or a 4 to make 57, and the values for two 23s (=46) and four 23s (=92) are automatically crossed out using this method.
It's actually very old - ancient in fact. The Ancient Egyptians used the method and documented it in around 1700 BC, but it may be a lot older than that. In 1960, the Belgian explorer Jean de Heinzelin de Braucourt found a notched piece of bone in the area of Ishango, in the modern-day border region between Uganda and Congo. An advanced society is believed to have existed there 20,000 years ago, but this was ended abruptly by a volcanic eruption. The pattern of notches on the Ishango Bone has not been explained conclusively, but it appears to describe a mathematical operation involving multiplication by two.
How the method got to Russia is a bit of a mystery, but it is thought Western visitors observed it there in the 19th Century. The Egyptian papyri describing the method were rediscovered later. The method is still used in parts of Africa today.
Computer Peasant Multiplication
These days, we civilised, super-educated folk tend to eschew such prehistoric methods as this, and happily conduct all our multiplication requirements using a pocket calculator or computer. It may come as a surprise, then, to discover that an almost identical binary multiplication algorithm is used by computers. We don't see this, of course; we use applications like calculators and spreadsheets which hide from us all the goings-on deep in the heart of the computer's arithmetic logic unit.
Computers work in binary, of course; every single piece of information - a character, a number, an image, or whatever - is represented by a string of binary digits. In our multiplication example, the computer would be storing numbers 57 and 23 as 111001 and 10111 respectively. When we instruct the computer to multiply them together, it will do it something like this:
Store 57 (111001) in an area of memory. We'll call this the multiplicand area.
Store 23 (10111) in another area of memory. We'll call this the multiplier area.
Clear a third area of memory to hold the result (copy zero into it).
If the last digit (bit) of the multiplicand is 1 (ie, it's an odd number), then add the multiplier to the result area. The multiplicand is indeed an odd number (57), so we add 23 to the result area: zero plus 23 = 23.
Divide the multiplicand by two by shifting all the binary digits one place to the right. This converts 111001 to 11100 - the last digit drops off the end. This is in fact the binary equivalent for the number 28.
Multiply the multiplier by two by shifting all its binary digits one place to the left. This converts 10111 to 101110 - we add a zero at the end. This is the binary equivalent for the number 46.
Keep repeating the previous three steps while the multiplicand is greater than 1. At each iteration, the computer will be storing the following numbers:
| Multiplicand Area | Multiplier Area | Result Area |
| 00111001 | 00010111 | 00000000 |
| Multiplicand Area | Multiplier Area | Result Area |
| 00011100 | 00101110 | 00010111 |
| Multiplicand Area | Multiplier Area | Result Area |
| 00000000 00111001 | 00000000 00010111 | 00000000 00000000 |
| 00000000 00011100 | 00000000 00101110 | 00000000 00010111 |
| 00000000 00001110 | 00000000 01011100 | 00000000 00010111 |
| 00000000 00000111 | 00000000 10111000 | 00000000 11001111 |
| 00000000 00000011 | 00000001 01110000 | 00000010 00111111 |
| 00000000 00000001 | 00000010 11100000 | 00000101 00011111 |
The computer's iteration loop stops after the multiplicand has reduced to 1, at which point we will have 57 x 23 stored in the result area. This will be in binary form (10100011111) rather than the decimal 1,311.
