Fast Multiplication

You learned to multiply in school by lining up digits and multiplying each digit of one number by every digit of the other. For two numbers with n digits, that is roughly n × n little multiplications — and for the three-digit numbers on your homework, nobody minds.

But computers multiply numbers with thousands or millions of digits: cryptographic keys, the digits of π, giant scientific computations. At that scale, n × n stops being a footnote and becomes the whole bill. Multiply the size by ten and the work grows by a hundred.

For two thousand years, the schoolbook method was multiplication — it seemed obvious that you simply had to combine every digit with every other digit. Then, in 1960, a student found a way to skip most of that work. The trick was so unexpected that his own advisor had publicly claimed it was impossible.

Both methods below compute the same product — checking that two algorithms agree is easy. What differs is the effort. Move the slider to set the number size n (in digits), and watch how many single-digit multiplications each method needs.

<p class="hint">{{hint}}</p>
<div class="row">
  <label for="n">{{size_label}} <b id="nval">8</b> {{digits_word}}</label>
  <input id="n" type="range" min="1" max="64" value="8" />
</div>
<div class="nums" id="nums"></div>
<div class="bars">
  <div class="bar-row"><span class="bl">{{schoolbook}}</span><div class="track"><div class="fill sb" id="sbBar"></div></div><span class="bv" id="sbVal">0</span></div>
  <div class="bar-row"><span class="bl">{{karatsuba}}</span><div class="track"><div class="fill kt" id="ktBar"></div></div><span class="bv" id="ktVal">0</span></div>
</div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="run" type="button">{{btn_multiply}}</button>
  <button id="rand" type="button" class="ghost">{{btn_new}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.row { margin: .5rem 0; font-size: .92rem; }
.row input[type=range] { width: 100%; margin-top: .3rem; }
.nums { font: 600 13px ui-monospace, monospace; color: #1d3557; background: #eef3f7;
        border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem .6rem; margin: .5rem 0;
        word-break: break-all; line-height: 1.5; min-height: 2.2em; }
.bars { margin: .6rem 0; }
.bar-row { display: flex; align-items: center; gap: .5rem; margin: .35rem 0; font-size: .85rem; }
.bl { width: 84px; flex: none; color: #444; }
.track { flex: 1; background: #e8eef3; border-radius: 6px; height: 20px; overflow: hidden; }
.fill { height: 100%; width: 0; border-radius: 6px; transition: width .35s ease; }
.fill.sb { background: #e63946; }
.fill.kt { background: #2a9d8f; }
.bv { width: 88px; flex: none; text-align: right; font: 600 13px ui-monospace, monospace; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the gap widen. Schoolbook always needs about $n^{2}$ digit-multiplications. Karatsuba splits each number in half and cleverly uses three half-size multiplications instead of four — so its cost grows like $n^{1}$.585. Small n? Barely a difference. Large n? The schoolbook bar runs off the chart while Karatsuba stays calm.

How fast can you multiply two n-digit numbers? This question has a clean, well-understood answer — multiplication lives firmly in the class P of efficiently solvable problems — but pinning down the exact speed took sixty years.

• Schoolbook: $O(n^{2})$. Every digit times every digit. Simple, and for two thousand years assumed to be the best possible.
• Karatsuba: $O(n^{1}.585)$. In 1960, Anatoly Karatsuba (then a student in Andrey Kolmogorov's seminar) showed you can multiply two halves with three products instead of four, recursing on each. The exponent is $\log_{2}3$ ≈ 1.585.
• Toom-Cook & Schönhage-Strassen. Generalizing the split pushes the exponent toward 1. Then in 1971 Schönhage and Strassen used the Fast Fourier Transform to reach $O(n \log n \log \log n)$ — for decades the practical champion for very large numbers.
• The 2019 breakthrough: $O(n \log n)$. David Harvey and Joris van der Hoeven gave an algorithm running in $O(n \log n)$, matching a long-conjectured lower bound. It is galactic — only faster for astronomically large inputs — but it settles the theory.

The lesson is not that multiplication is hard. It is that even a problem you mastered in grade school can hide enormous room for improvement — and that "the obvious method" is rarely the fastest. This is the optimistic flip side of P vs NP: some problems we can keep speeding up.

Multiplying big numbers is a primitive that almost everything else stands on:

• Cryptography: RSA and Diffie-Hellman multiply numbers hundreds or thousands of digits long, over and over. Faster multiplication means faster (and feasible) encryption.
• Big-number libraries: GMP and friends switch between schoolbook, Karatsuba, Toom-Cook and FFT methods depending on size — they pick the right tool per n.
• Computer algebra: multiplying polynomials and high-precision numbers reduces directly to integer multiplication.
• Record computations: every new record for the digits of π leans on the fastest multiplication available.

The same divide-and-conquer instinct — split the problem, recombine cheaply — drives algorithms far beyond arithmetic, from fast matrix multiplication to signal processing.

Multiplication looks finished — you learned it at seven and never thought about it again. Yet behind that tidy operation runs one of the great stories in algorithms: a student's 1960 trick that broke a two-thousand-year assumption, the FFT revolution of the 1970s, and a 2019 result that finally hit the conjectured speed limit of $O(n \log n)$.

So the next time something seems obviously as fast as it can be, remember Karatsuba. Checking that two answers match is easy; finding a fundamentally faster way to get the answer can take centuries — and is often still possible. For the harder cousin of this question, see P vs NP.