Karatsuba Algorithm | Brilliant Math & Science Wiki (2024)

The naive way to multiple numbers is commonly taught in elementary school.

Grade school multiplcation takes four multiplication steps

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 above--the familiar grade-school 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 base-10 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}\]

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)\) time--a 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]

See Also

Primes

• \(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 single-digit long (the base case).

Divide and conquer techniques come in when Karatsuba uses recursion to solve subproblems--for 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 left-most 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 two-bit 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 right-most 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\]

Here is a Python implementation of the Karatsuba algorithm for base-10 numbers.

 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627282930

from math import ceil, floor#math.ceil(x) Return the ceiling of x as a float, the smallest integer value greater than or equal to x.#math.floor(x) Return the floor of x as a float, the largest integer value less than or equal to x.def karatsuba(x,y): #base case if x < 10 and y < 10: # in other words, if x and y are single digits return x*y n = max(len(str(x)), len(str(y))) m = ceil(n/2) #Cast n into a float because n might lie outside the representable range of integers. x_H = floor(x / 10**m) x_L = x % (10**m) y_H = floor(y / 10**m) y_L = y % (10**m) #recursive steps a = karatsuba(x_H,y_H) d = karatsuba(x_L,y_L) e = karatsuba(x_H + x_L, y_H + y_L) - a - d return int(a*(10**(m*2)) + e*(10**m) + d)#print(karatsuba(12,12))#print(karatsuba(0,0))#print(karatsuba(1234,4321))#print(karatsuba(3141592653589793238462643383279502884197169399375105820974944592,# 2718281828459045235360287471352662497757247093699959574966967627))

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 Karatsuba--now 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 Toom-Cook 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 Toom-Cook 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]

• Schönhage–Strassen Algorithm
• Toom–Cook Algorithm

1. Demaine, E., Indyk, P., & Kellis, M. Karatsuba’s Algorithm. Retrieved May 29, 2016, from http://courses.csail.mit.edu/6.006/spring11/exams/notes3-karatsuba
2. Babai, L. Divide and Conquer: The Karatsuba–Ofman algorithm. Retrieved May 30, 2016, from http://people.cs.uchicago.edu/~laci/HANDOUTS/karatsuba.pdf
3. , . Toom–Cook multiplication. Retrieved May 30, 2016, from https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication
4. , . Schönhage–Strassen algorithm. Retrieved May 30, 2016, from https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm