Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Algorithms · Divide & Conquer

Three, Not Four.

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?

2. How does Karatsuba recover ad + bc without computing ad and bc separately?

3. Why does saving one multiplication per split change the overall complexity?

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).

The picture: three products and a subtraction

x = 1234 = a·100 + ba=12 b=34y = 5678 = c·100 + dc=56 d=78z2 = a·c672z0 = b·d2652(a+b)(c+d) = 46·1346164z1 = 6164 − 672 − 2652 = 2840672·10⁴ + 2840·10² + 2652 = 7006652
The page’s numbers. Schoolbook multiplication of the two halves needs four products (ac, ad, bc, bd); here the sum (a+b)(c+d) supplies ad + bc in one product, after subtracting the two products already in hand. Note the sums, 46 and 134, can be longer than a half: 134 has three digits.

Worked example, step by step

Multiply 1234 × 5678 with the page’s code. Each row is one call that splits (a call on a single digit just multiplies). “Leaf products” are its direct calls that bottomed out at a one-digit operand.

CallSplit a, b | c, dz2 = a·cz0 = b·dz1 = (a+b)(c+d) − z2 − z0Leaf productsResult
1234 × 567812, 34 | 56, 7867226526164 − 672 − 2652 = 2840—7006652
12 × 561, 2 | 5, 651233 − 5 − 12 = 161×5=5; 2×6=12; 3×11=33672
34 × 783, 4 | 7, 82132105 − 21 − 32 = 523×7=21; 4×8=32; 7×15=1052652
46 × 1344, 6 | 13, 45224170 − 52 − 24 = 944×13=52; 6×4=246164
10 × 171, 0 | 1, 7108 − 1 − 0 = 71×1=1; 0×7=0; 1×8=8170
check1234 × 5678 = 7006652

The top call needs three sub-products: 12×56 = 672, 34×78 = 2652 and 46×134 = 6164, and recombines them as 672·10⁴ + 2840·10² + 2652 = 7006652. In all, 5 calls split and 11 multiply single digits, 16 calls in total. Schoolbook would need 16 single-digit products; a perfectly even three-way split twice would need 9. This run used 11 because the middle product is not a clean 2×2: 46×134 has a three-digit operand, so its own middle call, 10×17, splits again. The saving per level is real but not exactly 3 of 4, and it only becomes dramatic as the numbers grow: at 1,024 digits, 59,049 leaf products against 1,048,576 for a 10-level split (3¹⁰ against 4¹⁰), about 17.8 times fewer.

Complexity and trade-offs

CaseTimeSpaceWhy
SchoolbookO(n²)O(1) beyond the resultEvery digit of one number times every digit of the other. Lowest overhead, best for small numbers.
KaratsubaO(n^1.585)O(n)Three half-size products per level: n^(log₂ 3). Extra additions and subtractions are linear.
Toom–Cook 3-wayO(n^1.465)O(n)Five products of third-size numbers: n^(log₃ 5). Larger constant, wins above Karatsuba’s range.
FFT-based (Schönhage–Strassen)O(n log n log log n)O(n)Multiplies by convolution. Large constant; only worth it for numbers with thousands of digits.
Harvey–van der Hoeven (2019)O(n log n)O(n)Asymptotically optimal known bound; not used in practice because the crossover is astronomically large.

Asymptotics hide the constants, which is why libraries combine methods: schoolbook below a tuned size, Karatsuba above it, then Toom–Cook, then FFT. The cut-offs depend on the machine, and they exist because Karatsuba’s extra additions and temporary buffers lose to a tight nested loop on small operands. The result also needs O(n) working memory, where schoolbook can multiply in place.

Common mistakes

  • Shifting by 10ⁿ instead of by twice the split

    The combine is z2·p² + z1·p + z0 with p = 10^(n//2). For an odd digit count, p² is not 10ⁿ. Using 10**n gives 80740642050 for 12345 × 67890; the right answer is 838102050.

  • Splitting each number at its own midpoint

    Both numbers must be cut at the same place, sized by the longer one, or the powers of ten no longer line up. Splitting 9999 and 99 at their own halves yields 1070091 instead of 989901.

  • Assuming (a+b) is still a half-size number

    Adding two halves can carry into a new digit: here 56 + 78 = 134 has three digits. The recursion must handle operands longer than the split, and a fixed-width implementation needs a spare bit or limb so the sum does not overflow.

  • Subtracting in the wrong order, or skipping the correction

    The middle term is (a+b)(c+d) − z2 − z0. Forgetting to subtract both leaves ad + bc + ac + bd; the middle term is too large by z2 + z0, which is multiplied by the shift p.

  • Recursing all the way down

    Below a certain size the recursion, the extra additions and the temporary numbers cost more than the multiplications they save. Production code stops at a tuned cut-off and uses schoolbook there. Karatsuba on one- and two-digit numbers is slower than *.

Where this shows up

  • Big-integer libraries

    Python’s built-in int switches to Karatsuba for large operands (the cut-off is KARATSUBA_CUTOFF in CPython’s source), and Java’s BigInteger uses Karatsuba above a threshold and Toom–Cook above a larger one. GMP layers Karatsuba, Toom–Cook and FFT multiplication by size.

  • Cryptography

    RSA and similar schemes multiply numbers hundreds to thousands of bits long, and exact arithmetic in factorials or Fibonacci numbers at huge indices produces numbers with millions of digits. In both, the multiplication algorithm sets the running time.

  • Polynomial multiplication

    A polynomial product has the same form as a digit-by-digit product, with coefficients in place of digits and no carries. The same three-products trick applies directly.

  • The same idea in matrices

    Strassen’s 1969 algorithm multiplies 2×2 block matrices with 7 products instead of 8, which gives O(n^2.807). Like Karatsuba, it trades extra additions for a multiplication saved at every level of recursion.

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
  1. Base case: if either number is a single digit, just multiply — recursion below that costs more than it saves.
  2. Split at half the digit count: x = a·10ʰ + b and y = c·10ʰ + d.
  3. The naive expansion is ac·10²ʰ + (ad + bc)·10ʰ + bd — four products.
  4. 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.
  5. 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.
  6. Use the same half for both numbers, computed from the longer one, or the powers of ten stop lining up.
CPython · WebAssembly

Keep going

Finished this one? 0 / 99 Algorithms done
NextFFT: Values, Not Coefficients Next on the “Multiplying faster than school” ladder · rung 2 of 3

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms