Karatsuba Simulation

Controls

Current Frame

Colors: z2 (high), z0 (low), z1 (middle adjustment). Splits highlight operand halves.

Step Detail

Pseudocode

1function karatsuba(x, y):
2  if small(x,y): return x*y
3  split x = x1*B + x0; y = y1*B + y0
4  z0 = karatsuba(x0, y0)
5  z1 = karatsuba((x0+x1),(y0+y1))
6  z2 = karatsuba(x1, y1)
7  return (z2*B^2) + ((z1 - z2 - z0)*B) + z0

Mechanism

Two direct products (high/high, low/low) plus one aggregated mixed product derive the middle term: z1 = (x1+x0)(y1+y0) - z2 - z0. This reduces multiplications, giving O(n^1.585) growth.