Karatsuba multiplication

Karatsuba multiplication is a technique for multiplying integers together which is very different from the traditional grade-school technique. Karatsuba multiplication is often taught in computer science classes and analyzed theoretically. For very large numbers, it at least theoretically does much better.

However, to be really sure, one must do some empirical comparisons. I have written a relatively efficient implementation of both grade-school and Karatsuba multiplication using C++. This page summarizes this work.

Send comments about this page to cburch at the domain cburch DOT com