Karatsuba Multiplication

Sub-quadratic integer multiplication using three recursive multiplications instead of four via clever algebraic rearrangement.

O(n^{1.585})

T(n)=3T(n/2)+O(n)

O(n)

Recursion + temps

Split-Recombine

Reduce 4 to 3 products

Split operands into high and low halves around midpoint digit length m.

Compute z2 = x1*y1, z0 = x0*y0, and mid via (x1+x0)(y1+y0)-z2-z0.

Assemble: z2 * B^(2m) + z1 * B^m + z0 with base-power shifts.

Use Cases

T(n) = 3T(n/2) + O(n)

Master Theorem => n^(log2 3) ~ n^1.585. Break-even vs classical occurs at moderate digit lengths depending on constants.

Threshold hybrid: switch to classical O(n^2) below small n to reduce overhead.
Add/subtract cost linear; memory reuse lowers allocations in optimized library versions.
Stepping stone to Toom-Cook splits and FFT-based multiplication (lower exponents).