Why it matters

Karatsuba was first sub-quadratic multiplication. Understanding shapes algorithm history.

Advertisement

The architecture

Split X = a*B + b, Y = c*B + d.

XY = ac*B^2 + (ad+bc)*B + bd.

Compute (a+b)(c+d) - ac - bd for cross term.

Karatsuba structureSplitX = aB+b, Y = cB+d3 multiplicationsac, bd, (a+b)(c+d)Combineshifts + addsT(n) = 3T(n/2) + O(n) gives O(n^log2(3)) ~= O(n^1.585)
Karatsuba.
Advertisement

How it works end to end

Standard: 4 recursive calls.

Karatsuba: 3 (save one via algebraic identity).

Base case: schoolbook for small n.