Karatsuba Multiplication

The Karatsuba algorithm is a divide-and-conquer approach to multiplying large numbers. Instead of the traditional method requiring four multiplications for numbers split in half, Karatsuba requires only three, reducing the asymptotic complexity from O(n²) to O(n^1.585).

Worked Example

Let's multiply 12 and 34 using the Karatsuba algorithm. We choose a base B = 10, meaning we split the numbers at the 10s place (m = 1).

Split the inputs:
- x = 12, so a = 1, b = 2 (since 12 = 1·10 + 2)
- y = 34, so c = 3, d = 4 (since 34 = 3·10 + 4)
Compute three recursive products:
- z₂ = a × c = 1 × 3 = 3
- z₀ = b × d = 2 × 4 = 8
- z₁ = (a + b) × (c + d) = (1 + 2) × (3 + 4) = 3 × 7 = 21
Recombine the results:
Product = z₂·B² + (z₁ - z₂ - z₀)·B + z₀
= 3·100 + (21 - 3 - 8)·10 + 8
= 300 + 10·10 + 8
= 408

Interactive Trace

You can explore the Karatsuba Multiplication module to see the full recursion tree.

Set the input integers. For example, choose Integer x as 1234 and Integer y as 5678.
Click the Step button to trace the recursive splits and products.
Notice how the inputs are divided into a, b, c, and d at each level until they fall below the base case limit of 10.
Click Finish to evaluate all branches and see the exact final integer product 7006652.

Limitations and Assumptions

This implementation uses base-10 splitting for illustrative clarity rather than the base-2 typical in computer hardware implementations. It accurately computes and combines products up to the native IEEE 754 safe integer limit (2⁵³ - 1). Because our inputs are heavily constrained (max 9999), all intermediate integer representations are exact. For numbers well beyond thousands of digits, an algorithm with even lower asymptotic complexity, such as Schönhage–Strassen or FFT-based multiplication, is preferable.

References

MIT 6.006 Integer Arithmetic & Karatsuba Multiplication

This lecture covers the derivation, correctness, and complexity analysis of Karatsuba's method for integer multiplication.

Karatsuba Multiplication