What is the Karatsuba algorithm?

The Karatsuba algorithm, developed by Anatoly Karatsuba in 1960, is a multiplication algorithm that uses a divide-and-conquer approach to multiply two large numbers, leading to a reduced number of recursive multiplications required and, hence, faster multiplication results.

Traditional algorithm vs. Karatsuba algorithm

The traditional grade school algorithm, also known as long multiplication, has a time complexity of $O(n^2)$ , where $n$ denotes the number of digits in the operands. The Karatsuba algorithm, on the other hand, offers a running time of $O(n^{log_23})$ or $O(n^{1.585})$ , allowing faster multiplication between two $n$ -bit numbers.

Steps

The karatsuba algorithm can be broken down into 3 steps; divide, conquer, and combine. Let's understand what happens at each of these steps when dividing two numbers X and Y:

Divide: In this step, we break both the numbers into two equal halves of lengths $n/2$ each.
X = X₁, X₂
Y = Y₁, Y₂
Conquer: In this step, we recursively compute the following three products of the $n/2$ -bit halves:
1. P₁ = X₁ * Y₁
2. P₂ = X₂ * Y₂
3. P₃ = (X₁ + X₂) * (Y₁ + Y₂) - P₁ - P₂
Combine: In the final step, we perform some additions to compute the final product XY as:
X * Y = P₁ * 10ⁿ + P₃ * 10^(n/2) + P₂

Example

Let's look at a simple example to understand the working of the Karatsuba algorithm:

def karatsuba(x, y):
    # Base case
    if x < 10 or y < 10:
        return x * y
    # Recursive case
    else:
        # Divide
        n = max(len(str(x)), len(str(y)))
        n_2 = n // 2
        
        x1, x2 = divmod(x, 10**n_2)
        y1, y2 = divmod(y, 10**n_2)
        # Conquer
        p1 = karatsuba(x1, y1)
        p2 = karatsuba(x2, y2)
        p3 = karatsuba((x1 + x2), (y1 + y2)) - p1 - p2
        # Combine
        result = p1 * 10**(2*n_2) + p3 * 10**n_2 + p2
        return result
print(karatsuba(1234, 5678)) # 7006652
print(karatsuba(15, 60)) # 900
print(karatsuba(987654, 123456)) # 121931812224

What is the Karatsuba algorithm?

Traditional algorithm vs. Karatsuba algorithm

Steps

Example

Code example

Conclusion