1. One-Liner
Karatsuba multiplies two n-digit numbers using three recursive multiplies on roughly n/2-digit halves plus additions—fewer multiplies than the schoolbook four quarter-products.
2. The Problem It Solves
Schoolbook long multiplication costs O(n²) digit multiplies; Karatsuba improves the asymptotic exponent for large n, underpinning fast big-integer libraries when tuned with thresholds and FFT for huge sizes.
3. The Core Idea
Write x = a·10^m + b, y = c·10^m + d. Instead of computing ac, ad, bc, bd separately for four products, compute z0=bd, z2=ac, and z1=(a+b)(c+d)−z0−z2—only three multiplications.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Split | Choose m = ⌊n/2⌋; split digits of x,y into high/low parts. |
| 2. Three products | z0, z1, z2 as above (recursive until base case). |
| 3. Combine | z2·10^{2m} + z1·10^m + z0. |
| 4. Base | Small operands → direct multiply. |
5. Dry Run Example
x=12, y=34 → a=1,b=2,c=3,d=4, m=1 → z0=8, z2=3, z1=(3)(7)−8−3=10 → 300+100+8=408.
6. Key Properties
| Property | Value |
|---|---|
| Time | O(n^{log_2 3}) ≈ O(n^{1.585}) digit ops |
| Space | Recursion depth O(log n) |
| Hybrid | Switch to schoolbook below a threshold |
7. Where It Is Used
| Domain | Use |
|---|---|
| Crypto / bigint | Fast multiplication in libraries (often + FFT at huge scale) |
| Competitive programming | Big integer challenges |
8. Interview Tips
Derive three products vs four; mention Toom–Cook and FFT as faster asymptotics for huge numbers; watch carry and split edge cases.
9. Comparison with Other Algorithms
| Method | Complexity | Notes |
|---|---|---|
| Schoolbook | O(n²) | Simple |
| Karatsuba | O(n^{1.585}) | Three-term trick |
| FFT-based | O(n log n) | Very large n |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n^{log_2 3}) |
| Space | O(log n) recursion typical |
Implementation Example (PYTHON)
def karatsuba(x, y):
if x < 10 or y < 10:
return x * y
sx, sy = str(x), str(y)
n = max(len(sx), len(sy))
m = n // 2
p = 10 ** m
a, b = divmod(x, p)
c, d = divmod(y, p)
z0 = karatsuba(b, d)
z2 = karatsuba(a, c)
z1 = karatsuba(a + b, c + d) - z2 - z0
return z2 * p * p + z1 * p + z0