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