Toom-Cook Multiplication...

Over the years I've written several “math packs” – collections of mathematical functions that can't be performed on the underlying computer's hardware.  Back in the bad old days of 8 bit microcomputers, this even included multiply and divide (the hardware could only add and subtract).  These days most computer hardware can handle 64 bit integer math and double precision IEEE floating point math (including the common transcendentals).  For integer math larger than 64 bits, though, math packs are still the order of the day.

Multiply and divide on integers much larger than the computer's hardware can handle are fairly complex operations.  In all the math packs I've written, the approach taken is the software equivalent of longhand multiplication and division (albeit in binary, not decimal).  This morning I came across an algorithm for multiply that is faster: the Toom-Cook multiplication algorithm.

One of the many fascinating things about the world of software is that new ideas are popping up all the time, even for hoary old algorithms that you might think were so basic they couldn't be improved...