Karatsuba Multiplication

Multiplies two n-digit numbers with only 3 recursive half-size multiplications instead of the 4 that grade-school long multiplication needs — the products z0, z1, z2 recombine algebraically to give the full result.

Category: Divide and Conquer
Time complexity: O(n^1.585)
Space complexity: O(n)

Pseudocode

split x, y into high/low halves at digit m
z0 = low1×low2, z2 = high1×high2
z1 = (low1+high1)×(low2+high2)
result = z2·10^2m + (z1−z2−z0)·10^m + z0

Reference implementation

def karatsuba(x, y):
    if x &lt; 10 or y &lt; 10: return x * y
    m = max(len(str(x)), len(str(y))) // 2
    hx, lx = divmod(x, 10**m)
    hy, ly = divmod(y, 10**m)
    z0 = karatsuba(lx, ly)
    z2 = karatsuba(hx, hy)
    z1 = karatsuba(lx+hx, ly+hy)
    return z2*10**(2*m) + (z1-z2-z0)*10**m + z0

Open the interactive Karatsuba Multiplication visualisation →