For numbers x and y with n digits:
• Split: x = a·10^m + b, y = c·10^m + d
• Compute: z₀ = b·d, z₂ = a·c
• Key insight: z₁ = (a+b)(c+d) - z₂ - z₀
• Result: x·y = z₂·10^(2m) + z₁·10^m + z₀
• Classical: O(n²) - n² digit multiplications
• Karatsuba: O(n^1.585) - only 3 recursive calls
• Improvement comes from reducing 4 multiplications to 3
• Enter two numbers to multiply
• Click "Next Step" to begin
• Step through the algorithm visualization
• Complete challenges to test understanding as you progress through the algorithm
• Compare with classical multiplication
Standard grade-school method requires n² single-digit multiplications for n-digit numbers.
Reduces the number of recursive multiplications from 4 to 3 using clever algebraic manipulation.
Instead of computing ac, ad, bc, bd separately:
This gives us z₁ = ad + bc with only 3 multiplications!