Karatsuba Multiplication
Fast multiplication algorithm for large integers using divide-and-conquer. Discovered by Anatoly Karatsuba in 1960, it was the first algorithm to demonstrate multiplication can be done faster than O(n²). Reduces three recursive multiplications instead of four, achieving O(n^log₂3) ≈ O(n^1.585) complexity.
Visualization
Interactive visualization for Karatsuba Multiplication
Interactive visualization with step-by-step execution
Implementation
1function karatsuba(x: bigint, y: bigint): bigint {
2 // Base case
3 if (x < 10n || y < 10n) {
4 return x * y;
5 }
6
7 const n = Math.max(x.toString().length, y.toString().length);
8 const m = Math.floor(n / 2);
9 const power = 10n ** BigInt(m);
10
11 const a = x / power;
12 const b = x % power;
13 const c = y / power;
14 const d = y % power;
15
16 const z0 = karatsuba(a, c);
17 const z2 = karatsuba(b, d);
18 const z1 = karatsuba(a + b, c + d) - z0 - z2;
19
20 return z0 * (10n ** BigInt(2 * m)) + z1 * power + z2;
21}Deep Dive
Theoretical Foundation
For two n-digit numbers x and y, split each into two halves: x = a·10^(n/2) + b, y = c·10^(n/2) + d. Standard multiplication computes ac, ad, bc, bd (4 multiplications). Karatsuba computes only: z0=ac, z2=bd, z1=(a+b)(c+d)-z0-z2=ad+bc. Result: z0·10^n + z1·10^(n/2) + z2. This reduces 4 multiplications to 3, giving better asymptotic complexity.
Complexity
Time
O(n^1.585)
O(n^1.585)
O(n^1.585)
Space
O(log n) recursion depth
Applications
Industry Use
Cryptographic systems (RSA, elliptic curves)
Arbitrary precision arithmetic libraries
Scientific computing with large numbers
Computer algebra systems
Competitive programming contests
Digital signal processing
Number theory research
Use Cases
Related Algorithms
Merge Sort (Divide & Conquer Paradigm)
Classic divide-and-conquer sorting algorithm that recursively divides array into halves until single elements, then merges sorted subarrays. Invented by John von Neumann in 1945, it's one of the most efficient general-purpose sorting algorithms with guaranteed O(n log n) performance. The algorithm perfectly demonstrates the divide-and-conquer paradigm: divide problem, solve subproblems recursively, combine solutions.
Binary Search (Divide & Conquer)
Efficient search algorithm for sorted arrays using divide-and-conquer. At each step, eliminate half of remaining elements by comparing target with middle element. One of the most fundamental algorithms in computer science with O(log n) time complexity.
Closest Pair of Points
Find two points with minimum Euclidean distance among n points in 2D plane using divide-and-conquer. Naive O(n²) approach checks all pairs; divide-and-conquer achieves O(n log n) by recursively finding closest pairs in left/right halves and checking split pairs efficiently.
Closest Pair of Points
Find two closest points in 2D plane. Divide-and-conquer approach achieves O(n log n). Classic algorithm demonstrating geometric divide-and-conquer.