Karatsuba Multiplication
Multiply n-digit numbers with three half-size products instead of four.
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.
What you will see
Digits split in halves; three recursive products combine with shifts.
Cost
| Best | O(n^1.585) |
|---|---|
| Average | O(n^1.585) |
| Worst | O(n^1.585) |
| Space | O(n) |
Exponent is log2(3).
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input.
Screen readers: Each call frame announces its range and result; each step announces split, recurse or combine.
Reduced motion: Frames appear and disappear with crossfades; ranges highlight without motion.
Before this
Taught by the same lesson
Karatsuba and Strassen covers these too, in the same run.