Karatsuba Multiplication Algorithm
You'll learn how to multiply large numbers faster by cleverly reducing the number of operations needed at each recursive step.
When you multiply two large numbers the traditional way (the "grade school" method), you multiply each digit of one number by each digit of the other. For n-digit numbers, this takes O(n²) time—it grows quadratically.
The Karatsuba algorithm uses divide-and-conquer to do better. Here's the clever insight:
Instead of treating a number as a pile of digits to multiply individually, split each number into two halves. For example, if you're multiplying 1234 × 5678, think of them as:
- 1234 = 12 × 10² + 34
- 5678 = 56 × 10² + 78
The naive approach would do four multiplications (high×high, high×low, low×high, low×low). But Karatsuba discovered you only need three multiplications by being clever with addition and subtraction:
- Multiply the high parts:
a = high₁ × high₂ - Multiply the low parts:
b = low₁ × low₂ - Multiply the sums:
c = (high₁ + low₁) × (high₂ + low₂)
Then the middle term equals c - a - b. Combine these with appropriate powers of 10, and you get the full answer.
By reducing four multiplications to three at each level, and recursing on smaller numbers, the time complexity improves from O(n²) to approximately O(n^1.585). This matters enormously for cryptography and scientific computing with thousand-digit numbers.
Key Takeaway: Karatsuba multiplication splits large numbers in half and uses just three recursive multiplications instead of four, achieving better-than-quadratic performance through a clever algebraic trick.