Karatsuba Algorithm
The Karatsuba algorithm is a fast multiplication algorithm that uses a divide and conquer approach to multiply two numbers. The naive algorithm for multiplying two numbers has a running time of \(\Theta\big(n^2\big)\) while this algorithm has a running time of \(\Theta\big(n^{\log_2 3}\big)\approx \Theta\big(n^{1.585}\big)\). Being able to multiply numbers quickly is very important. Computer scientists often consider multiplication to be a constant time \(O(1)\) operation, and this is a reasonable simplification for smaller numbers; but for larger numbers, the actual running times need to be factored in, which is \(O\big(n^2\big)\). The point of the Karatsuba algorithm is to break large numbers down into smaller numbers so that any multiplications that occur happen on smaller numbers. Karatsuba can be used to multiply numbers in all base systems (base10, base2, etc.).
Contents
Naive Multiplication Algorithm
The naive way to multiple numbers is commonly taught in elementary school.
Here’s the naive multiplication algorithm to multiply two \(n\)bit numbers, \(x\) and \(y\) that are in base \(b\).
Divide each number into two halves, the high bits \(H\) and the low bits \(L:\)
\[x = x_Hb^{\frac{n}{2}} + X_L, \quad y = y_Hb^{\frac{n}{2}} + Y_L.\]
Multiply the two numbers together:
\[\begin{align} xy &= \big(x_Hb^{\frac{n}{2}} + X_L\big) \times \big(y_Hb^{\frac{n}{2}} + Y_L\big)\\ &= x_Hy_Hb^n + (x_Hy_L + x_Ly_H)b^{\frac{n}{2}} + x_Ly_L. \end{align}\]
These formulas describe what is going on in the image abovethe familiar gradeschool way of multiplying numbers. This has four multiplications: \(x_Hy_Hb^n\), \((x_Hy_L)b^{\frac{n}{2}}\), \((x_Ly_H)b^{\frac{n}{2}}\), and \(x_Ly_L,\) which has a running time of \(O(n^2)\).
Let's use this method to multiply the base10 numbers \(1234\) and \(8765:\)
\[\begin{align} x &= x_Hb^{\frac{n}{2}} + X_L \\ &= 12 \times 10^2 + 34\\\\ y &= y_Hb^{\frac{n}{2}} + Y_L\\ &= 87 \times 10^2 + 65\\\\ xy &= \big(x_Hb^{\frac{n}{2}} + X_L\big) \times \big(y_Hb^{\frac{n}{2}} + Y_L\big)\\ &= (12 \times 10^2 + 34) \times (87 \times 10^2 +65)\\ &= x_Hy_Hb^n + (x_Hy_L + x_Ly_H)b^{\frac{n}{2}} + x_Ly_L\\ &= 12 \times 87 \times 10^4 + (12 \times 65 + 34 \times 87)\times 10^2 + (65 \times 34)\\ & = 10,816,010. \end{align}\]
Karatsuba Algorithm
The Karatsuba algorithm decreases the number of subproblems to three and ends up calculating the product of two \(n\)bit numbers in \(\Theta\big(n^{\log_2 3}\big)\) timea vast improvement over the naive algorithm.
To multiply two \(n\)bit numbers, \(x\) and \(y\), the Karatsuba algorithm performs three multiplications and a few additions, and shifts on smaller numbers that are roughly half the size of the original \(x\) and \(y\).
Here’s how the Karatsuba method works to multiply two \(n\)bit numbers \(x\) and \(y\) which are in base \(b\).
Create the following three subproblems where \(H\) represents the high bits of the number and \(L\) represents the lower bits:^{[1]}
 \(a = x_Hy_H\)
 \(d = x_Ly_L\)
 \(e = (x_H + x_L)(y_H + y_L)  a d \)
 \(xy = ab^n + eb^{\frac{n}{2}} + d.\)
This only requires three multiplications and has the recurrence \[3T\left(\frac{n}{2}\right) + O(n) = O\left(n^{\log 3}\right).\] Karatsuba can be applied recursively to a number until the numbers being multiplied are only a singledigit long (the base case).
Divide and conquer techniques come in when Karatsuba uses recursion to solve subproblemsfor example, if multiplication is needed to solve for \(a\), \(d\), or \(e\) before those variables can be used to solve the overall \(x \times y\) multiplication.
Perform the following multiplication using the Karatsuba method: \(1234 \times 4321\).^{[1]}
First, determine the \(a\) value for step 1, \(a_1\)this will contain the high bits of \(x\) and \(y\) since \(x\) and \(y\) have four bits, and the leftmost two are the high bits.\(a_1 = 12 \times 43\). Note, we will have to call the Karatsuba algorithm on \(a_1\) since a multiplication is necessary to obtain the value (this time, a twobit multiplication). Before we recurse, though, let’s find \(d_1\) and \(e_1\).
\(d\) contains the lower bits of each number since \(x\) and \(y\) have four bits, and the lower bits in this problem are the two rightmost bits.
\(d_1 = 34 \times 21\). Note, we will also have to recurse on \(d_1\) to obtain the value.
Recall that \(e= (x_H + x_L)(y_H + y_L)  a d \).
\(e_1 = (12 + 34) \times (43+21)  a_1  d_1\). Now we are stuck and can’t simplify \(e_1\) further until we have the values of \(a_1\) and \(d_1\), so it is time to recurse.
Solving for \(a_1:\)
We have \[\begin{align} a_1 &= 12 \times 43\\ a_2 &= 1 \times 4 = 4\\ d_2 &= 2 \times 3 = 6\\ e_2 &= (1+2)(4+3)  a_2  d_2\\ &= (1+2)(4+3)  4  6\\ &= 11. \end{align}\] Recall that \(xy = ar^n + er^{\frac{n}{2}} + d.\) Therefore, \(a_1 = 12 \times 43 = 4 \times 10^2 + 11 \times 10 + 6 = 516\).
Solving for \(d_1:\)
We have \[\begin{align} d_1 &= 34 \times 21\\ a_2 &= 3 \times 2 = 6\\ d_2 &= 4 \times 1 = 4\\ e_2 &= (3 + 4)(2+1)  a_2  d_2 \\&= 11. \end{align}\] Since \(xy = ar^n + er^{\frac{n}{2}} + d,\) \(d_1 = 34 \times 21 = 6 \times 10^2 + 11 \times 10 + 4 = 714\).
Solving for \(e_1:\)
We have \[\begin{align} e_1 &= (46 \times 64)  a_1  d_1\\ a_2 &= 4 \times 6 = 24\\ d_2 &= 6 \times 4 = 24\\ e_2 &= (4+6)(6+4)  a_2  d_2 \\&= 52. \end{align}\] Since \(xy = ar^n + er^{\frac{n}{2}} + d,\) \(e_1 = (46 \times 64)  a_1  d_1 = 24 \times 10^2 + 52 \times 10 + 24  714  516= 1714\).
Now we can get the answer to the original problem as follows:
We have \[a_1 = 516,\quad d_1 = 714,\quad e_1 = 1714.\] Plugging into \(xy = ar^n + er^{\frac{n}{2}} + d\), we get \[xy = (516)10^4 + (1714)10^{2} + 714 = 5,332,114.\ _\square\]
Implementation of the Karatsuba Algorithm
Here is a Python implementation of the Karatsuba algorithm for base10 numbers.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 

Complexity of Karatsuba
To analyze the complexity of the Karatsuba algorithm, consider the number of multiplications the algorithm performs as a function of \(n\), \(M(n)\). Recall that the algorithm multiplies together two \(n\)bit numbers. If \(n=2^k\) for some \(k\), then the algorithm recurses three times on \(\frac{n}{2}\)bit number. The recurrence for this is
\[M(n) = 3M\left(\frac{n}{2}\right).\]
This takes care of the multiplications required for Karatsubanow to consider the additions and subtractions. There are \(O(n)\) additions and subtractions required for the algorithm. Therefore, the overall recurrence for the Karatsuba algorithm is^{[2]}
\[T(n) = 3T\left(\frac{n}{2}\right) + O(n).\]
Using the master theorem on the above recurrence yields that the running time of the Karatsuba algorithm is \(\Theta\big(n^{\log_2 3}\big)\approx \Theta\big(n^{1.585}\big).\)
The Schönhage–Strassen algorithm and the Toom–Cook algorithm are other popular integer multiplication algorithms. The ToomCook algorithm is faster, more generalized version of the Karatsuba algorithm that runs in \(\Theta\left(n^{\frac{\log 5}{\log 3}}\right) \approx \Theta\big(n^{1.465}\big)\).^{[3]} The Schönhage–Strassen algorithm is faster than both Karatsuba and ToomCook for very large \(n\) \(\big(\)on the order of \(n > 2^{2^{15}}\big)\) and runs in \(O(n \log n \log \log n)\).^{[4]}
See Also
References
 Demaine, E., Indyk, P., & Kellis, M. Karatsuba’s Algorithm. Retrieved May 29, 2016, from http://courses.csail.mit.edu/6.006/spring11/exams/notes3karatsuba
 Babai, L. Divide and Conquer: The Karatsuba–Ofman algorithm. Retrieved May 30, 2016, from http://people.cs.uchicago.edu/~laci/HANDOUTS/karatsuba.pdf
 , . Toom–Cook multiplication. Retrieved May 30, 2016, from https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication
 , . Schönhage–Strassen algorithm. Retrieved May 30, 2016, from https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm