Karatsuba Multiplication
Replace four half-size products with three and reconstruct an exact integer product.
Free theory articleReplace four half-size products with three and reconstruct an exact integer product.
Concept & interpretation
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(n2) to O(n1.585).
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.