Long multiplication of two n-digit numbers costs O(n²) — every digit times every digit. Split each number into a high half and a low half and you’d expect four half-size products. Karatsuba’s 1960 insight: you only need three. Compute the high·high and low·low products, then get the cross term from a single extra product — (aₕ+aₗ)(bₕ+bₗ) minus the two you already have. Recursing that 4→3 saving compounds, dropping multiplication to about O(n^1.585). Step through and watch three products replace four.
O(n^log₂3) ≈ O(n^1.585) · 3 sub-products per split, not 4 · divide and conquer
split
Write each number as high·B + low, where B is a power of 10 at the midpoint.
z2, z0
The high·high product (z2) and low·low product (z0) — two of the three.
z1 (the trick)
(high+low)(high+low) − z2 − z0 gives the cross term with one product, not two.
combine
Result = z2·B² + z1·B + z0 — shift and add the three products.
karatsuba.js — one product saved per split
Ready
Multiplying two 2-digit numbers. Split each into a tens digit and a units digit. Schoolbook would do 4 single-digit products; Karatsuba does only 3. Step to build them.
0
products used
4
schoolbook
–
result
How it works
Write x = a·B + b and y = c·B + d. Then x·y = ac·B² + (ad+bc)·B + bd — four products (ac, ad, bc, bd). Karatsuba keeps ac and bd, but notices the middle coefficient ad+bc can be recovered from a single new product: (a+b)(c+d) = ac + ad + bc + bd, so ad+bc = (a+b)(c+d) − ac − bd. Three multiplications, one subtraction, instead of four multiplications. The extra additions are cheap (linear), and when this is applied recursively to each half, the saved multiplication is what bends the exponent from 2 down to log₂3 ≈ 1.585.
1
Split both numbers
Write x = a·B + b and y = c·B + d, splitting each at the midpoint (here B = 10, so a,b,c,d are single digits).
2
Two corner products
Compute z2 = a·c (the high part) and z0 = b·d (the low part). These are two of the three multiplications.
3
The clever middle product
Compute z1 = (a+b)·(c+d) − z2 − z0. This one product yields the full cross term ad+bc that schoolbook needed two products for.
✓
Shift and add
Combine: result = z2·B² + z1·B + z0. Three multiplications total. Recursing the same 4→3 saving on each half gives O(n^1.585).
Time
O(n^1.585)
Products / split
3 (not 4)
vs schoolbook
O(n²)
Year
1960
The code
# Karatsuba: 3 multiplications per split (recurses on each)def karatsuba(x, y):
if x < 10 or y < 10: return x * y # base case
B = 10 ** (max(len(str(x)), len(str(y))) // 2)
a, b = divmod(x, B) # high, low of x
c, d = divmod(y, B) # high, low of y
z2 = karatsuba(a, c) # 1
z0 = karatsuba(b, d) # 2
z1 = karatsuba(a + b, c + d) - z2 - z0 # 3 (not 4!)return z2 * B*B + z1 * B + z0
Quick check
1. How many sub-multiplications does Karatsuba use per split, and how many does schoolbook use?
Schoolbook splitting needs four half-size products (ac, ad, bc, bd). Karatsuba computes ac and bd, then gets the cross term from one more product (a+b)(c+d) minus the two — three total.
2. How does Karatsuba recover ad + bc without computing ad and bc separately?
Expanding (a+b)(c+d) gives ac + ad + bc + bd. Subtracting the already-computed ac and bd leaves exactly ad + bc — the middle coefficient — from a single extra multiplication.
3. Why does saving one multiplication per split change the overall complexity?
The recurrence T(n) = 3·T(n/2) + O(n) solves to O(n^log₂3) ≈ O(n^1.585) by the master theorem. Doing 3 instead of 4 subproblems at every level is what lowers the exponent.
FAQ
What is Karatsuba multiplication?
A divide-and-conquer algorithm for multiplying large numbers faster than schoolbook O(n²). It splits each number in half and computes only three half-size products instead of four — recovering the cross term from one extra product — running in about O(n^1.585) recursively.
How much faster is Karatsuba than long multiplication?
Long multiplication is O(n²); Karatsuba is ≈ O(n^1.585). For small numbers the overhead makes schoolbook faster, so implementations use Karatsuba only above a threshold (tens to hundreds of digits). For very large numbers it is substantially faster.
Is Karatsuba the fastest multiplication algorithm?
No. It was the first to beat O(n²), but Toom–Cook (more split parts) and FFT-based methods (Schönhage–Strassen, and the O(n log n) Harvey–van der Hoeven) are faster for very large numbers. Karatsuba stays popular for being simple and fast in the mid-size range.
Where is Karatsuba used?
Big-integer libraries (behind Python’s int, Java’s BigInteger, GMP) for numbers above a size threshold, and anywhere large-number multiplication matters — cryptography, computer algebra, high-precision math. Libraries combine schoolbook (small), Karatsuba (medium), and FFT (largest).
SOLVE IT YOURSELF
Solve it: multiply with three products, not four
Splitting two numbers in half needs four sub-multiplications — unless you notice the middle term can be recovered from the other three. That one observation drops the exponent from 2 to 1.585. Python or TypeScript.
YOUR TASK
Implement karatsuba(x, y) for non-negative integers, using exactly three recursive multiplications per level instead of the obvious four.
HINTS — 6 IDEAS
Base case: if either number is a single digit, just multiply — recursion below that costs more than it saves.
Split at half the digit count: x = a·10ʰ + b and y = c·10ʰ + d.
The naive expansion is ac·10²ʰ + (ad + bc)·10ʰ + bd — four products.
The trick: (a+b)(c+d) = ac + ad + bc + bd, so ad + bc = (a+b)(c+d) − ac − bd. You already have ac and bd, so the middle term is free.
Three recursive calls instead of four turns O(n²) into O(n^1.585) — the first algorithm to beat long multiplication, and a genuine surprise when Karatsuba found it.
Use the same half for both numbers, computed from the longer one, or the powers of ten stop lining up.