Hacking Multiplication With Karatsuba’s Algorithm

People tend to obsess over making computer software faster. You can, of course, just crank up the clock speed and add more processors, but often the most powerful way to make something faster is to find a better way to do it. Sometimes those methods are very different from how a human being would do the same task, but it suits the computer’s capabilities. [Nemean] has a video explaining a better multiplication algorithm known as Karatsuba’s algorithm and it is actually quite clever. You can see the video below.

To help you understand the algorithm, the video shows a simple two-digit by two-digit multiplication. You can see that the first and last digits are essentially the result of one multiplication. It is all the intermediate digits that add together. The only thing that might change the first digit is a carry.

Continue reading “Hacking Multiplication With Karatsuba’s Algorithm”

Hacking Multiplication: Binary Multiply On Paper

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”

Inside Mechanical Calculators

For as busy as things can get at the grocery store on a typical afternoon just before the dinner hour, at least the modern experience has one thing going for it: it’s relatively quiet. Aside from the mumbled greetings and “Paper or plastic?” questions from the cashier, and the occasional screaming baby in the next aisle, the only sound you tend to hear is the beeping of the barcode scanner as your purchase is tallied up.

Jump back just 40 years and the same scene was raucous, with cashiers reading price tags and pounding numbers into behemoth electromechanical cash registers. Back then, if you wanted help with any arithmetic with more than just a few operations, some kind of mechanical calculator was your only choice. From simple “one-banger” adding machines to complex analog computers, mechanical devices were surprisingly capable data processing tools. Here’s a brief look at how some of the simpler ones worked.

Continue reading “Inside Mechanical Calculators”