The Russian Peasant Algorithm

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.

Add comment

Security code
Refresh