Karatsuba Multiplication

For thousands of years, multiplying two large numbers meant one thing: add up rows of partial products, one digit at a time. Schoolbook long multiplication of two n-digit numbers takes roughly $n^{2}$ individual digit multiplications. For small numbers that's fine; for the enormous integers used in cryptography, scientific computing, or large prime searches, it becomes the bottleneck.

In 1960, the great mathematician Andrei Kolmogorov conjectured that $n^{2}$ was a fundamental lower bound — that no algorithm could do better. Within a week, a 23-year-old student named Anatoly Karatsuba proved him wrong. Karatsuba published the result in 1962, and it became the first algorithm to break the $O(n^{2})$ barrier for integer multiplication.

The insight is a single algebraic trick: split each number in half, then recover the four necessary partial products using only three recursive multiplications instead of four. Additions are cheap; multiplications are what you want to minimize. One saved multiplication per level of recursion, compounded across all levels, bends the exponent from 2 down to approximately 1.585.

This is solved and well-understood: Karatsuba's algorithm runs in $O(n^{\log_2 3})$ $\approx$ $O(n^{1.585})$ time (proven by Karatsuba and Ofman, 1962). It was the opening move in a long story that eventually led to algorithms approaching $O(n \log n)$ via FFT-based methods. But Karatsuba's elementary divide-and-conquer insight remains the cleanest illustration of how a single algebraic identity can rewrite the rules of computation.

Enter two numbers below and press Multiply. The demo walks through Karatsuba's divide-and-conquer split step by step, showing the three recursive sub-multiplications and how they are combined to get the final product.

<div class="controls">
  <label>A: <input id="numA" type="number" value="1234" min="0" max="99999999" step="1"></label>
  <label>B: <input id="numB" type="number" value="5678" min="0" max="99999999" step="1"></label>
  <button id="btnMultiply" type="button">{{btn_multiply}}</button>
  <button id="btnRandom" type="button" class="ghost">{{btn_random}}</button>
</div>
<div id="result" class="result hidden"></div>
<div id="steps" class="steps"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; gap: .6rem; flex-wrap: wrap; align-items: center; margin-bottom: .8rem; }
label { display: flex; align-items: center; gap: .35rem; font-size: .95rem; font-weight: 600; }
input[type=number] { width: 110px; padding: .35rem .5rem; font: 600 .95rem ui-monospace,monospace;
  border: 1.5px solid #c0c8d4; border-radius: 6px; }
button { font: 600 14px system-ui,sans-serif; padding: .4rem .9rem; border: 1.5px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { background: #e8f4ea; border: 1.5px solid #4caf50; border-radius: 8px;
          padding: .55rem .9rem; font: 700 1.05rem ui-monospace,monospace; color: #1b5e20;
          margin-bottom: .7rem; }
.result.hidden { display: none; }
.steps { display: flex; flex-direction: column; gap: .5rem; }
.step { background: #f0f4f8; border-left: 3px solid #1d3557; border-radius: 0 6px 6px 0;
        padding: .45rem .75rem; font-size: .88rem; line-height: 1.55; }
.step.base { border-color: #4caf50; background: #f0faf1; }
.step .label { font-weight: 700; color: #1d3557; margin-bottom: .15rem; }
.step .label.base { color: #2e7d32; }
.step code { font-family: ui-monospace,monospace; background: #dde5ef; border-radius: 3px;
             padding: 0 3px; font-size: .87em; }
.step .sub { color: #555; margin-top: .1rem; }
.highlight { color: #c0392b; font-weight: 700; }

// Code not found

Notice that each level splits the work into three smaller multiplications instead of four. Schoolbook would need four multiplications at each split: a·c, a·d, b·c, b·d. Karatsuba computes a·c, b·d, and one extra product (a+b)·(c+d), then recovers the middle term a·d + b·c by subtraction — saving one multiplication per level in exchange for a handful of additions.

To understand why Karatsuba is faster, compare the two recurrences:

• Schoolbook: $T(n) = 4 \cdot T(n/2) + O(n)$ $\to$ $T(n) = O(n^{2})$
• Karatsuba: $T(n) = 3 \cdot T(n/2) + O(n)$ $\to$ $T(n) = O(n^{\log_2 3})$ $\approx$ $O(n^{1.585})$

The difference of just one recursive call changes everything. The Master Theorem tells us that the number of sub-problems (3 vs 4) directly sets the exponent: $\log_{2}4 = 2$ gives $O(n^{2})$, while $\log_{2}3 \approx 1.585$ gives the Karatsuba bound.

For concrete intuition: multiply two 1024-digit numbers.

• Schoolbook: ~1,048,576 digit-multiplications ($n^{2}$)
• Karatsuba: $\approx 1024^{1.585} \approx$ 59,000 multiplications — 18× fewer

The gain grows with n: at 10,000 digits, schoolbook needs 100 million operations while Karatsuba needs roughly 2.4 million.

Is $O(n^{1.585})$ optimal? No. The story continued:

• Toom-Cook (1963): generalizes the split to k parts, reaching $O(n^{1.465})$ and beyond.
• Schönhage-Strassen (1971): uses Fast Fourier Transforms to reach $O(n \log n \log \log n)$.
• Harvey-Hoeven (2019): achieves $O(n \log n)$ — the conjectured optimal.

But Karatsuba's is the one that is simple enough to implement by hand and powerful enough to appear in Python's int, Java's BigInteger, and GMP (the GNU Multiple Precision library). It kicks in once numbers exceed roughly 70 digits, and that threshold is used everywhere from browser JavaScript engines to RSA cryptography.

Karatsuba's algorithm sits quietly inside software you use every day:

• Arbitrary-precision arithmetic: Python's built-in int switches to Karatsuba at ~70 decimal digits. Java's BigInteger does the same. The GNU MP library (GMP), used by virtually every language runtime that needs big numbers, implements Karatsuba and Toom-Cook.
• Cryptography: RSA, Diffie-Hellman, and elliptic-curve protocols multiply 2048- to 4096-bit integers constantly. Karatsuba is the workhorse for these key sizes; FFT-based methods only become competitive above ~10,000 bits.
• Polynomial multiplication: multiplying polynomials of degree n has the same structure as integer multiplication. Karatsuba's method applies directly, and it underlies fast polynomial arithmetic in computer algebra systems like Mathematica and SageMath.
• Convolutions in signal processing: the same divide-and-conquer pattern appears in computing convolutions, with applications from audio processing to image filtering.

The broader lesson is the same one that runs through all of fast multiplication: once you see arithmetic as a structured splitting problem, cheap operations (additions, subtractions) can substitute for expensive ones (multiplications), and the savings compound across every recursive level.

Karatsuba's algorithm is a lesson in what an identity can be worth. The equation

$$a \cdot d + b \cdot c = (a+b)(c+d) - a \cdot c - b \cdot d$$

looks unremarkable — it is just algebra. But applied recursively, it replaces a four-way split with a three-way split, and that single change drops the exponent of n from 2 to 1.585 across all recursion levels.

Kolmogorov had conjectured the $O(n^{2})$ barrier was real. Karatsuba refuted it in days. The insight sparked half a century of improvements — Toom-Cook, Schönhage-Strassen, and finally Harvey and Hoeven's 2019 $O(n \log n)$ algorithm — but the core principle of trading one multiplication for two additions has never been bettered at the elementary level.

The next time Python computes 10**1000 * 10**1000 in a blink, you know why: somewhere beneath the surface, Karatsuba's trick is quietly splitting, multiplying three times, and adding the pieces back together — saving one multiplication per level, all the way down.