Karatsuba Multiplication Calculator
Multiply large integers using the Karatsuba divide-and-conquer algorithm.
Enter Numbers
Karatsuba Formula
For x = x₁·10^m + x₀ and y = y₁·10^m + y₀:
z₀ = x₀ · y₀
z₂ = x₁ · y₁
z₁ = (x₀+x₁)(y₀+y₁) - z₀ - z₂
xy = z₂·10^(2m) + z₁·10^m + z₀
Complexity
Traditional: O(n²)
Karatsuba: O(n^log₂3) ≈ O(n^1.585)
Uses only 3 multiplications instead of 4!
1234 × 5678
= 7,006,652
Complexity Comparison
Algorithm Steps
Split at m=2:
1234 = 12·10^2 + 34
5678 = 56·10^2 + 78
Split at m=1:
34 = 3·10^1 + 4
78 = 7·10^1 + 8
Combine:
21·10^2 + 52·10^1 + 32 = 2652
Split at m=1:
12 = 1·10^1 + 2
56 = 5·10^1 + 6
Combine:
5·10^2 + 16·10^1 + 12 = 672
Split at m=1:
46 = 4·10^1 + 6
134 = 13·10^1 + 4
Split at m=1:
10 = 1·10^1 + 0
17 = 1·10^1 + 7
Combine:
1·10^2 + 7·10^1 + 0 = 170
Combine:
52·10^2 + 94·10^1 + 24 = 6164
Combine:
672·10^4 + 2840·10^2 + 2652 = 7006652
Verification
Direct: 7,006,652
Results match!