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) ```