### Russian Peasant Multiplication and other algorithms

Today was the third day of my algorithms class. I talked about a couple of algorithms for standard arithmetic problems. One was Euclid's greatest common divisor algorithm. Another was russian peasant multiplication.

To multiply two numbers N and M together using russian peasant multiplication, you follow these steps:

I first learned about russian peasant multiplication when I was a nerdy little kid reading math books. I absorbed it fairly well, and believe it should be taught in K-12 schools. There is some opposition to teaching non-traditional algorithms in grade school arithmetic, but RPM has a benefit that other algorithms don't have. It is the way computers do multiplication. Computers work in base 2, so multiplication and division by 2 (the only arithmetic operations other than addition used here) are unusually fast. They can be done with a shift operation.

Kids don't have to be taught all the details I gave above. But it might pique their interest in computers, and it would plant a memory that would be useful later if they took computer architecture.

The lady in the video below makes a pretty good case against alternative algorithms. I could argue with some of her points, and just might do that in a later post. Right now, my response to her would be to ask for just one non-standard algorithm which might be beneficial to students.

To multiply two numbers N and M together using russian peasant multiplication, you follow these steps:

- If N is odd, add M to a subtotal (which will eventually contain the product).
- Divide N by 2, dropping any remained. Multiply M by 2.
- If N is equal to 1, the subtotal is equal to the product and you are done. Otherwise go to step 1.

N | M | Value To Be Added | Subtotal |
---|---|---|---|

19 | 13 | 13 | 13 |

9 | 26 | 26 | 39 |

4 | 52 | 0 | 39 |

2 | 104 | 0 | 39 |

1 | 208 | 208 | 247 |

I first learned about russian peasant multiplication when I was a nerdy little kid reading math books. I absorbed it fairly well, and believe it should be taught in K-12 schools. There is some opposition to teaching non-traditional algorithms in grade school arithmetic, but RPM has a benefit that other algorithms don't have. It is the way computers do multiplication. Computers work in base 2, so multiplication and division by 2 (the only arithmetic operations other than addition used here) are unusually fast. They can be done with a shift operation.

Kids don't have to be taught all the details I gave above. But it might pique their interest in computers, and it would plant a memory that would be useful later if they took computer architecture.

The lady in the video below makes a pretty good case against alternative algorithms. I could argue with some of her points, and just might do that in a later post. Right now, my response to her would be to ask for just one non-standard algorithm which might be beneficial to students.

## Comments