**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**

Hi, things like getting input as integers and using functions may be a trouble for beginners, so here is a “running off the shelf” version: https://repl.it/CBno

LikeLike

Thank you so much for the “writing n as 2*nby2” tip. Without it, just using 10**n * (a * c), the algorithm works for all four-digit numbers (as far as I can tell), but fails on about one eight-digit problem out of eight, more with higher numbers of digits. I had found that the failures were related to getting an odd number of digits with a split, since leading zeros are dropped (45670123 splits as 4567 and 123), and had been trying to fix it by going to strings and padding out leading zeros. That actually reduced the failure rate, but fails still occurred. Your simple fix removed the whole issue!

LikeLike

Hi,

I found your implementation amusing because of the usage of / and % operators as they take more time than the actual problem

Did you test your results for large size inputs?

I believe those operators should be replaced by string concatenation for an efficient implementation

LikeLike

Hi, thanks for the 2*nby2 tip! However i’m a noob and still don’t understand how it works. Is it because python remembers that for odd numbers, the nby2 is actually a float and accounts for that when doing the multiplication?

Thanks!

LikeLike