We’ve often noted that whether had ancient man known binary, we could all count to 1023 on our fingers. We thought about that while watching [Numberphile’s] latest video about “Russian” multiplication (see below). Apparently, the method dates back quite a way, sometimes known as Ethiopian or peasant multiplication. Even the ancient Egyptians did a form of it.

If you’ve ever written long multiplication code for a microcontroller, you can probably tell how this works. Each halving of the number amounts to a right shift. Each doubling is a left shift. Throwing out the even numbers means you only take the values when the least-significant bit is zero. Booth’s algorithm is more efficient, but the “Russian” method is simple to do on paper.

Continue reading “Hacking Multiplication: Binary Multiply On Paper” →