Karatsuba Multiplication
Multiply n-digit numbers with three half-size products instead of four.
Karatsuba and Strassen: Karatsuba: 1234 x 5678 with three products
The middle term needs a d + b c. Instead of two products, multiply the sums once: (12 + 34) x (56 + 78) = 46 x 134 = 6164, which expands to a c + a d + b c + b d. Subtract the two products already known, 672 and 2652, and what remains is exactly a d + b c: z1 = 2840. Three multiplications, not four.
Cost
- Best
- O(n^1.585)
- Average
- O(n^1.585)
- Worst
- O(n^1.585)
- Space
- O(n)
Exponent is log2(3).
Before this
Taught by the same lesson
Karatsuba and Strassen covers these too, in the same run.