?

Log in

AlbertJayNock

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

NMValue To
Be Added
Subtotal
19131313
9262639
452039
2104039
1208208247





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.





Tags: ,

Comments