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 (base-10, base-2, etc.).

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]

• \(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]

Show Answer

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
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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