04
Karatsuba Multiplication
Chapter 4 • Advanced
90 min
Karatsuba Multiplication
Problem Statement
Multiply two n-digit numbers efficiently.
Naive Multiplication
python.js
def multiply_naive(x, y):
"""
Standard multiplication: O(n²)
"""
if x < 10 or y < 10:
return x * y
# Convert to strings for digit access
x_str = str(x)
y_str = str(y)
n = max(len(x_str), len(y_str))
# Pad with zeros
x_str = x_str.zfill(n)
y_str = y_str.zfill(n)
result = 0
for i in range(len(y_str)):
for j in range(len(x_str)):
result += int(x_str[j]) * int(y_str[i]) * (10 ** (n - 1 - i - j))
return result
Karatsuba Algorithm
Key Insight
For x = a·10^(n/2) + b and y = c·10^(n/2) + d:
x·y = (a·10^(n/2) + b)(c·10^(n/2) + d)
= ac·10^n + (ad + bc)·10^(n/2) + bd
But: (a + b)(c + d) = ac + ad + bc + bd
So: ad + bc = (a + b)(c + d) - ac - bd
We only need 3 multiplications: ac, bd, (a+b)(c+d)
Implementation
python.js
def karatsuba(x, y):
"""
Karatsuba multiplication: O(n^log₂(3)) ≈ O(n^1.585)
"""
# Base case
if x < 10 or y < 10:
return x * y
# Calculate number of digits
n = max(len(str(x)), len(str(y)))
m = n // 2
# Split numbers
power = 10 ** m
a = x // power
b = x % power
c = y // power
d = y % power
# Recursive calls
z0 = karatsuba(b, d)
z1 = karatsuba((a + b), (c + d))
z2 = karatsuba(a, c)
# Combine results
return z2 * (10 ** (2 * m)) + (z1 - z2 - z0) * (10 ** m) + z0
Complexity Analysis
Recurrence: T(n) = 3T(n/2) + O(n)
Using Master Theorem:
- a = 3, b = 2, f(n) = n
- log_b a = log₂ 3 ≈ 1.585
- f(n) = O(n) = O(n^(log_b a - ε)) for ε > 0
- Case 1: T(n) = Θ(n^(log₂ 3)) ≈ Θ(n^1.585)
Comparison
| Method | Time Complexity |
|---|---|
| Naive | O(n²) |
| Karatsuba | O(n^1.585) |
| FFT-based | O(n log n) |
Example
python.js
x = 1234
y = 5678
# Split: a=12, b=34, c=56, d=78
# z0 = 34 * 78 = 2652
# z1 = (12+34) * (56+78) = 46 * 134 = 6164
# z2 = 12 * 56 = 672
# Result = 672*10000 + (6164-672-2652)*100 + 2652
# = 6720000 + 28400 + 2652 = 7006652
Practice Problems
- Implement Karatsuba multiplication
- Compare performance with naive method
- Extend to negative numbers
- Optimize for small inputs
- Implement for arbitrary precision