Karatsuba Multiplication — Three Products Instead of Four

Split x = a·B + b and y = c·B + d, compute z2 = a·c, z0 = b·d, and z1 = (a+b)(c+d) − z2 − z0, then recombine z2·B² + z1·B + z0. Three multiplications give T(n)=3T(n/2)+O(n)=O(n1.585).

step 0

Split into high / low halves

x = 1234 a=12 b=34
y = 5678 c=56 d=78
z2 = a·c —
z0 = b·d —
p = (a+b)(c+d) —
z1 = p − z2 − z0 —
z2 (high · B²) z1 (middle · B) z0 (low · B⁰)

Recombine with shifts

x·y = z2·B² + z1·B + z0
= —·B² + —·B + —
= —

Three products, not four

naive: 4 mults Karatsuba: 3 exponent n² (4 mults) n^1.585 (3 mults)
Recurrence T(n) = 3T(n/2) + O(n) → O(n^log₂3) ≈ O(n^1.585). The saved 4th multiplication is recovered by addition/subtraction (cheap, O(n)).
Press Step to begin. We split each number into a high half and a low half, then compute the product with only three multiplications.
Self-contained visualization. Decimal base B = 10half; values are exact (no modulus). For integers, recombination additions may carry — try 99 × 99 where z1 = 162 overflows a base-10 slot. See junior.md and professional.md for the derivation and the recurrence solution.