The Russian Peasant Algorithm

It's only fair to share...Share on FacebookTweet about this on TwitterPin on PinterestShare on Google+Share on RedditEmail this to someone

The Russian Peasant Algorithm multiplies two numbers together. The steps are:

1. Write down the two numbers in the two columns of a table.

2. Divide the number in column 1 by 2 and write the result in the second row below the first number, ignoring decimals and remainders.

3. Multiply the number in column 2 by two and write the answer below the second number in column 2.

4. Repeat steps 2 and 3 until the last number in the first column is 1.

5. Delete every row that has an even number in column 1.

6. Add up the numbers in column 2 that have not been crossed out. The result is the product of the two numbers.

55 53
27 106
13 212
6 424
3 848
1 1696

Dividing 55 successively by 2 and ignoring the remainder gives 27, 13, 6, 3, 1.

Delete row 4 containing an (even) 6.

55 53
27 106
13 212
3 848
1 1696

Add up the numbers in column 2 that are not crossed out to give 53+106+212+848+1696=2915.

This is indeed equal to 55*53.

 

Comments are closed.