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.