Karatsuba Multiplication Visualization | 3 Products Instead of 4

The idea: three half-size products instead of four

Schoolbook multiplication of two n-digit numbers multiplies every digit of one by every digit of the other: n² digit products. Splitting each number in half does not help by itself. With x = a·10^m + b and y = c·10^m + d,

x·y = a·c·10^2m + (a·d + b·c)·10^m + b·d

needs four half-size products, and four problems of half the size is the same n² work. In 1960 Anatoly Karatsuba noticed that the middle term needs only one more product:

z2 = a·c        z0 = b·d        p = (a + b)(c + d)
z1 = p − z2 − z0            # = a·d + b·c
x·y = z2·10^2m + z1·10^m + z0

1234 is split into a = 12 and b = 34, 5678 into c = 56 and d = 78. Three products: z2 = 12 × 56 = 672, z0 = 34 × 78 = 2652, p = 46 × 134 = 6164. Then z1 = 6164 − 672 − 2652 = 2840, and 672·10⁴ + 2840·10² + 2652 = 7006652. — One split of 1234 × 5678: three half-size products, then only subtractions, shifts and additions.

The algorithm

karatsuba(x, y):
    if x < 10 or y < 10: return x * y          # base case
    m = max(digits(x), digits(y)) // 2
    a, b = divmod(x, 10**m);  c, d = divmod(y, 10**m)
    z2 = karatsuba(a, c)
    z0 = karatsuba(b, d)
    p  = karatsuba(a + b, c + d)
    return z2 * 10**(2*m) + (p - z2 - z0) * 10**m + z0

The canvas draws the tree of calls. A call turns amber, splits, and its three children appear. Each child is solved in turn (depth first), and its value flies back to its row in the this call panel. When all three are back, the call computes z1 and combines. Blue is z2 = a·c, green is z0 = b·d, purple is p = (a+b)(c+d), everywhere on the page. The smallest case shows the trick: 12 × 34 makes the calls 1 × 3, 2 × 4 and 3 × 7, so z1 = 21 − 3 − 8 = 10 and the answer is 300 + 100 + 8 = 408. (Demo: 12 × 34, one split)

1234 × 5678 splits at m = 2 into 12 × 56, 34 × 78 and 46 × 134, and those split once more. The result 7006652 takes 16 calls and 11 base-case multiplies. The plain split on the same numbers takes 21 calls and 16 base multiplies, as many as the 4 × 4 schoolbook digit products. (Demo: 1234 × 5678, two levels of splits and Demo: 1234 × 5678 with 4 products per call)

Why 3 instead of 4 matters

Splitting, shifting and adding n-digit numbers cost O(n). So the two methods have these recurrences:

method	recurrence	leaves for n = 2^k	total
schoolbook	—	n² digit products	O(n²)
plain split, 4 products	T(n) = 4T(n/2) + O(n)	4^k = n²	O(n²)
Karatsuba, 3 products	T(n) = 3T(n/2) + O(n)	3^k = n^log₂3	O(n^1.585)

Each level of the tree has 3 times as many calls on numbers half as long, so the work per level grows by 3/2. The leaves dominate: 3^{log₂ n} = n^{log₂ 3} ≈ n^1.585. By the Master Theorem, a = 3, b = 2 and f(n) = n is case 1. For 1024 digits that is 59,049 small products instead of 1,048,576.

Two recursion trees by level for n-digit numbers. Plain split: 1, 4, 16, 64 calls on n, n/2, n/4, n/8 digits, the work per level doubles: n, 2n, 4n, 8n, and the 4^k leaves give n². Karatsuba: 1, 3, 9, 27 calls; the work per level grows n, 1.5n, 2.25n, 3.375n, and the 3^k leaves give n^1.585. — Four children per call keep n² leaves; three children leave n^log₂3 ≈ n^1.585.

The carry, and why small numbers lose

a + b can be one digit longer than a or b. 99 × 99 splits into 9 × 9, 9 × 9 and 18 × 18, and 18 × 18 must split again: 7 calls and 5 base multiplies, while the plain split needs only 4. (Demo: 99 × 99, a carry in a + b) 9999 × 9999 is the largest tree the page allows: 28 calls, depth 4 and 19 base multiplies against 16. (Demo: 9999 × 9999, the largest tree) The saving of one product in four only wins once the numbers are long enough to pay for the extra additions and carries.

Uneven lengths need no special case: m comes from the longer number, so in 1234 × 56 the high half c of 56 is 0, and the call 12 × 0 is a base case.

In practice

Big-number libraries use Karatsuba only above a cutoff and schoolbook below it. CPython's int multiplies with Karatsuba when both numbers have more than KARATSUBA_CUTOFF = 70 machine digits (of 30 bits each). GMP measures its thresholds per CPU and goes on to Toom-Cook (Toom-3 splits into 3 parts with 5 products: O(n^1.465)) and then FFT multiplication (Schönhage–Strassen, O(n log n log log n)) for very large numbers. In 2019 Harvey and van der Hoeven reached O(n log n). The same "fewer products, more additions" idea gives Strassen's algorithm for matrices: 7 half-size products instead of 8 (see Matrix Multiplication).

See also The Recursion Tree and the Master Theorem, Big-O growth, Quick Sort vs Merge Sort for another divide-and-conquer, and Fourier Series and the FFT.

Divide and conquer also works in geometry: the closest pair of points splits the points at the middle x and checks only a strip around the line.

What the page leaves out

Numbers are capped at 4 decimal digits so the whole tree fits on the canvas; real libraries work in base 2³⁰ or 2⁶⁴ "limbs". The base case is "a factor is a single digit", as in the textbook version, not a tuned cutoff. Negative numbers, the variant that uses (a − b)(d − c) to avoid the carry, the cost of the additions themselves, Toom-Cook and FFT multiplication are described but not animated.

See where this page fits on the Recursion mind map.