Karatsuba Integer Multiplication (Divide & Conquer)
Problem
- Multiply two large integers faster than the naive O(n^2) schoolbook algorithm.
Key idea (intuition)
- Split each n-digit number into high and low halves. Instead of four multiplications of halves, compute only three recursive multiplications using the identity:
z2 = high1 * high2z0 = low1 * low2z1 = (high1 + low1) * (high2 + low2) - z2 - z0Combine with appropriate digit shifts to form the full product. This reduces multiplicative work.
Complexity
- Time: O(n^{log2(3)}) ≈ O(n^{1.585})
- Space: O(n) (depending on representation and recursion depth)
Worked example
1234 * 5678 = 7006652The implementation uses string-based splitting and recursive multiplication; it is primarily educational to show divide-and-conquer speedup.
Notes
- For very large numbers and production code, use FFT-based multiplication (Schönhage–Strassen) or big-integer libraries.
Code: main.cpp — recursive Karatsuba implementation.