**Motivation for this blog post**

I’ve enrolled in Stanford Professor *Tim Roughgarden’s* Coursera MOOC on the **design and analysis of algorithms, **and while he covers the theory and intuition behind the algorithms in a surprising amount of detail, we’re left to implement them in a programming language of our choice.

**And I’m ging to post Python code for all the algorithms covered during the course!**

**The Karatsuba Multiplication Algorithm**

Karatsuba’s algorithm reduces the multiplication of two *n*-digit numbers to at most single-digit multiplications in general (and exactly when *n* is a power of 2). Although the familiar **grade school algorithm** for multiplying numbers is how we work through multiplication in our day-to-day lives, it’s slower () in comparison, but only on a computer, of course!

Here’s how the **grade school algorithm** looks:

*(The following slides have been taken from Tim Roughgarden’s notes. They serve as a good illustration. I hope he doesn’t mind my sharing them.)*

…and this is how **Karatsuba Multiplication** works on the same problem:

**A More General Treatment**

Let and be represented as -digit strings in some base . For any positive integer less than , one can write the two given numbers as

,

where and are less than . The product is then

where

These formulae require four multiplications, and were known to Charles Babbage. **Karatsuba** observed that can be computed in only three multiplications, at the cost of a few extra additions. With and as before we can calculate

which holds since

A more efficient implementation of Karatsuba multiplication can be set as , where .

**Example**

To compute the product of 12345 and 6789, choose *B* = 10 and *m* = 3. Then we decompose the input operands using the resulting base (*B*^{m} = *1000*), as:

- 12345 =
**12**·*1000*+**345** - 6789 =
**6**·*1000*+**789**

Only three multiplications, which operate on smaller integers, are used to compute three partial results:

*z*_{2}=**12****×****6**= 72*z*_{0}=**345****×****789**= 272205*z*_{1}= (**12**+**345**)**×**(**6**+**789**) −*z*_{2}−*z*_{0}= 357**×**795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

We get the result by just adding these three partial results, shifted accordingly (and then taking carries into account by decomposing these three inputs in base *1000* like for the input operands):

- result =
*z*_{2}·*B*^{2m}+*z*_{1}·*B*^{m}+*z*_{0}, i.e. - result = 72 ·
*1000*^{2}+ 11538 ·*1000*+ 272205 =**83810205**.

**Pseudocode and Python code**