AlgoScope

Karatsuba Multiplication

Multiply n-digit numbers with three half-size products instead of four.

Divide and conquer, algorithm, advanced
z1 is 6164 minus 672 minus 2652, which is 2840.highlowxyz2 = a cz0 = b d(a+b)(c+d)z1x y12345678672265246 x 13461646164 - 672 - 26522840
z1 is 6164 minus 672 minus 2652, which is 2840.highlowxyz2 = a cz0 = b d(a+b)(c+d)z1x y12345678672265246 x 13461646164 - 672 - 26522840

Karatsuba and Strassen: Karatsuba: 1234 x 5678 with three products

Decision, step 3 of 4

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).

Taught by the same lesson

Karatsuba and Strassen covers these too, in the same run.