Karatsuba Multiplication

The Karatsuba algorithm is a fast multiplication algorithm that uses divide-and-conquer to multiply two numbers in O(n^1.58) time.

Step 1 / 53

x:12345678

y:87654321

High Parts (x1, y1)

z2 = -

Low Parts (x0, y0)

z0 = -

Middle Term (z1)

z1 = -

Entering Karatsuba for x=12345678, y=87654321

Input Numbers

Multiplier (X)

Multiplicand (Y)

Algorithm Invariants

Base Formula

$x = x_1 10^m + x_0$

$y = y_1 10^m + y_0$

The Trick ($z_1$)

By computing $(x_1+x_0)(y_1+y_0)$, we get $x_1 y_1 + x_1 y_0 + x_0 y_1 + x_0 y_0$.

Subtracting $z_2$ and $z_0$ leaves only the middle term ($x_1 y_0 + x_0 y_1$).

Growth$n^1.585$

Algorithm Logic

Pseudocode

1function Karatsuba(x, y):
2  if x < 10 or y < 10:
3    return x * y
4  n = max(length(x), length(y))
5  m = floor(n / 2)
6  x1, x0 = split(x, m)
7  y1, y0 = split(y, m)
8  z2 = Karatsuba(x1, y1)
9  z0 = Karatsuba(x0, y0)
10  z1 = Karatsuba(x1 + x0, y1 + y0) - z2 - z0
11  return z2 * 10^(2*m) + z1 * 10^m + z0