Karatsuba's multiplication algorithm is a [[divide-and-conquer]] algorithm for multiplying binary numbers.
Recall that to multiply two binary numbers $n$ and $m$ we can use grade school multiplication, working from the least significant digit in $m$, multiplying the digit by $n$, padding by one digit for each digit in $m$, and finally summing the $m$ sub results. The resulting array will be of size $m + n$.
To solve this with divide-and-conquer, divide the array into subarrays recursively where each subarray is padded by multiplying by $2^k$, which equates to $k$ zeros in binary. This ensures that when recombined the digits maintain their appropriate order.
For two arrays $a$ and $b$ split into two subarrays $1$ (upper half) and $2$ (lower half)
$ab = 2^na_1b_1 + 2^{n/2} \Big( a_1b_2 + a_2b_1 \Big) + a_2b_2$
The algorithm recurrence is
$T(n) = 4T \Big( \frac{n}{2} \Big) + \Theta(n)$
which solves to $\Theta(n^2)$. However, this is no better than grade school multiplication.
Karatsuba's trick saves one recurrence by recognizing that
$(a_1 + a_2)(b_1 + b_2) = a_1b_1 + \Big [a_2b_1 + a_1b_2 \Big]+ a_2b_2$
The term in the middle (set off by square brackets) is equivalent to the term in the middle of the divide-and-conquer grade school algorithm. Thus we can get one multiplication for free if we add the two halves of each binary number $a$ and $b$! We simply need to subtract the other products we are already calculating, $a_1b_1$ and $a_2b_2$.
The run time for Karatsuba's algorithm is
$T(n) = 3T \Big( \frac{n}{2} \Big) + \Theta(n)$
which solves to $\Theta(n^{\lg 3})$ where $\lg 3 \approx 1.54$. As $n$ increases this becomes substantially faster than the grade school algorithm.
The implementation in [[Python]] is below. Note that this code relies on some basic [[operations on binary numbers]].
```python
def karatsuba_multiply(a, b):
(m, n) = len(a), len(b)
if m <= 2 or n <= 2:
# revert to grade school multiplication
return grade_school_multiply(a, b)
else:
mid1 = m//2
a1 = a[0:mid1]
a2 = a[mid1:]
b1 = b[0:mid1]
b2 = b[mid1:]
# [a] = 2^{mid1} * [a2] + [a1]
# [b] = 2^{mid1} * [b2] + [b1]
# [a]* [b] = 2^{2*mid1} ([a2]*[b2]) + 2^mid1 ([a2]*[b1] + [a2]*[b1]) + [a1]*[b1]
# 3 recursive calls to karatsuba_multiply
r1 = karatsuba_multiply(a1, b1)
r2 = karatsuba_multiply(a2, b2)
r3 = karatsuba_multiply(add(a1, a2), add(b1, b2))
# Do subtraction
r4a = subtract(r3, r1)
r4 = subtract(r4a, r2)
# Do paddding
s1 = pad(r2, 2*mid1)
s2 = pad(r4, mid1)
s3 = add(s1, s2)
return add(s3, r1)
```