# Karatsuba Multiplication Algorithm – Python Code

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 $n^{\log_23}\approx n^{1.585}$ single-digit multiplications in general (and exactly $n^{\log_23}$ 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 ( $\Theta(n^2)\,\!$) 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 $x$ and $y$ be represented as $n$-digit strings in some base $B$. For any positive integer $m$ less than $n$, one can write the two given numbers as $x = x_1B^m + x_0$ $y = y_1B^m + y_0$,

where $x_0$ and $y_0$ are less than $B^m$. The product is then $xy = (x_1B^m + x_0)(y_1B^m + y_0)$ $xy = z_2B^{2m} + z_1B^m + z_0$

where $z_2 = x_1y_1$ $z_1 = x_1y_0 + x_0y_1$ $z_0 = x_0y_0$

These formulae require four multiplications, and were known to Charles Babbage. Karatsuba observed that $xy$ can be computed in only three multiplications, at the cost of a few extra additions. With $z_0$ and $z_2$ as before we can calculate $z_1 = (x_1 + x_0)(y_1 + y_0) - z_2 - z_0$

which holds since $z_1 = x_1y_0 + x_0y_1$ $z_1 = (x_1 + x_0)(y_1 + y_0) - x_1y_1 - x_0y_0$

A more efficient implementation of Karatsuba multiplication can be set as $xy = (b^2 + b)x_1y_1 - b(x_1 - x_0)(y_1 - y_0) + (b + 1)x_0y_0$, where $b = B^m$.

### 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 (Bm = 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:

z2 = 12 × 6 = 72
z0 = 345 × 789 = 272205
z1 = (12 + 345) × (6 + 789) − z2z0 = 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 = z2 · B2m + z1 · Bm + z0, i.e.
result = 72 · 10002 + 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
view raw karatsuba.py hosted with ❤ by GitHub