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

procedure karatsuba(num1, num2) | |

if (num1 < 10) or (num2 < 10) | |

return num1*num2 | |

/* calculates the size of the numbers */ | |

m = max(size_base10(num1), size_base10(num2)) | |

m2 = m/2 | |

/* split the digit sequences about the middle */ | |

high1, low1 = split_at(num1, m2) | |

high2, low2 = split_at(num2, m2) | |

/* 3 calls made to numbers approximately half the size */ | |

z0 = karatsuba(low1,low2) | |

z1 = karatsuba((low1+high1),(low2+high2)) | |

z2 = karatsuba(high1,high2) | |

return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0) |

def karatsuba(x,y): | |

"""Function to multiply 2 numbers in a more efficient manner than the grade school algorithm""" | |

if len(str(x)) == 1 or len(str(y)) == 1: | |

return x*y | |

else: | |

n = max(len(str(x)),len(str(y))) | |

nby2 = n / 2 | |

a = x / 10**(nby2) | |

b = x % 10**(nby2) | |

c = y / 10**(nby2) | |

d = y % 10**(nby2) | |

ac = karatsuba(a,c) | |

bd = karatsuba(b,d) | |

ad_plus_bc = karatsuba(a+b,c+d) - ac - bd | |

# this little trick, writing n as 2*nby2 takes care of both even and odd n | |

prod = ac * 10**(2*nby2) + (ad_plus_bc * 10**nby2) + bd | |

return prod |