BBC Home

Explore the BBC

Front Page

Life | The Universe | Everything | Advanced Search
 
Front PageReadTalkContributeHelp!FeedbackWho is Online

Click here to complete your registration.

 
3. Everything / Maths, Science & Technology / Mathematics

Russian Peasant Multiplication

Some Russian dolls.

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:

  1. 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.

  2. Halve the first number and write the result below it. Ignore any fractions, so 57 halved is 28.

  3. Double the second number and write the result below it, so 23 doubled is 46.

  4. 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.

  5. 5723
    2846
    1492
    7184
    3368
    1736

  6. 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.

  7. 5723
    ------
    ------
    7184
    3368
    1736
    Total:1,311

  8. 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.

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).

  • Multiplicand AreaMultiplier AreaResult Area
    001110010001011100000000

  • 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.

  • Multiplicand AreaMultiplier AreaResult Area
    000111000010111000010111

  • 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 AreaMultiplier AreaResult Area
    00000000 0011100100000000 0001011100000000 00000000
    00000000 0001110000000000 0010111000000000 00010111
    00000000 0000111000000000 0101110000000000 00010111
    00000000 0000011100000000 1011100000000000 11001111
    00000000 0000001100000001 0111000000000010 00111111
    00000000 0000000100000010 1110000000000101 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.


Discuss this Entry  People have been talking about this Guide Entry. Here are the most recent Conversations:

Nice. But why is it called Russian Peasant Multiplication?
(Last Posting: Mar 29, 2009)

You've added a picture!
(Last Posting: Jun 15, 2007)

Excellent Stuff
(Last Posting: Feb 17, 2009)




Add your Opinion!

There are tens of thousands of h2g2 Guide Entries, written by our Researchers. If you want to be able to add your own opinions to the Guide, simply become a member as an h2g2 Researcher. Tell me More!

 
Entry Data
Entry ID: A22808126 (Edited)

Written and Researched by:
Icy North

Edited by:
Atlantic_Cable


Date: 15   June   2007


Text only
Like this page?
Send it to a friend


Referenced Guide Entries
Computers
Numbers
World Population
Mathematics
Belgium
A History of Numbers
Fractions
The Union of Soviet Socialist Republics
How to Make Paper
Binary Digits
Conditional Statements and Loops in Programming
Zero


Most of the content on this site is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here to alert our Moderation Team. For any other comments, please start a Conversation below.
 


Front PageReadTalkContributeHelp!FeedbackWho is Online

Most of the content on h2g2 is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here. For any other comments, please start a Conversation above.


About the BBC | Help | Terms of Use | Privacy & Cookies Policy