Introduction

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.

Try It: Race the Methods

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">Two random <b>n</b>-digit numbers, multiplied two ways. Both give the <b>same product</b> (easy to check) — but count the single-digit multiplications each method spends (hard part). Schoolbook grows like n²; Karatsuba like n^1.585.</p>
<div class="row">
  <label for="n">Number size n = <b id="nval">8</b> digits</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">Multiply & count</button>
  <button id="rand" type="button" class="ghost">New numbers</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Compare the cost of multiplying two n-digit numbers.
//  - Schoolbook: ~n*n single-digit multiplications  (O(n^2))
//  - Karatsuba : splits in half, 3 half-size products (O(n^1.585))
// Both produce the SAME product (checked with BigInt). Counting one-digit
// multiplications is a clean proxy for the real running time.

let A = '', B = '';

function randDigits(n){
  let s = '';
  for (let i = 0; i < n; i++){
    let d = Math.floor(Math.random() * 10);
    if (i === 0 && d === 0) d = 1 + Math.floor(Math.random() * 9); // no leading zero
    s += d;
  }
  return s;
}

// Schoolbook: count digit*digit multiplications = exactly len(a)*len(b).
function schoolbookCount(a, b){ return a.length * b.length; }

// Karatsuba: split each number in half and use THREE half-size products
// instead of four. Like real libraries, fall back to schoolbook below a
// small cutoff (so it is never worse than schoolbook). We count single-digit
// multiplications. The 3-vs-4 saving is what bends the growth to n^1.585.
function karatsubaCountN(n){
  if (n <= 2) return n * n;             // tiny: schoolbook is cheaper
  const high = Math.ceil(n / 2);        // size of the larger half
  const tri = 3 * karatsubaCountN(high);
  return Math.min(tri, n * n);          // never lose to schoolbook
}
function karatsubaCount(a, b){ return karatsubaCountN(Math.max(a.length, b.length)); }

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

function newNums(){
  const n = +document.getElementById('n').value;
  A = randDigits(n); B = randDigits(n);
  document.getElementById('nums').innerHTML =
    'A = ' + A + '<br>B = ' + B;
  setStatus('', '');
  document.getElementById('sbBar').style.width = '0';
  document.getElementById('ktBar').style.width = '0';
  document.getElementById('sbVal').textContent = '0';
  document.getElementById('ktVal').textContent = '0';
}

function run(){
  if (!A) newNums();
  const sb = schoolbookCount(A, B);
  const kt = karatsubaCount(A, B);
  // Verify both methods agree on the actual product (the "easy to check" part).
  const product = (BigInt(A) * BigInt(B)).toString();

  const max = Math.max(sb, kt, 1);
  document.getElementById('sbBar').style.width = (100 * sb / max) + '%';
  document.getElementById('ktBar').style.width = (100 * kt / max) + '%';
  document.getElementById('sbVal').textContent = sb.toLocaleString();
  document.getElementById('ktVal').textContent = kt.toLocaleString();

  const saved = sb > 0 ? Math.round(100 * (1 - kt / sb)) : 0;
  setStatus(fmt('Same product (%length% digits). Karatsuba used %saved%% fewer digit-multiplications.', { length: product.length, saved: saved }), 'ok');
  console.log('product =', product);
  console.log('schoolbook digit-mults =', sb, '| karatsuba =', kt);
}

document.getElementById('n').addEventListener('input', function(){
  document.getElementById('nval').textContent = this.value;
  newNums();
});
document.getElementById('run').addEventListener('click', run);
document.getElementById('rand').addEventListener('click', function(){ newNums(); });
newNums();
Result
Console

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

The Real Complexity

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(n2)O(n^{2}). Every digit times every digit. Simple, and for two thousand years assumed to be the best possible.
  • Karatsuba: O(n1.585)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⁡23\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(nlog⁡nlog⁡log⁡n)O(n \log n \log \log n) — for decades the practical champion for very large numbers.
  • The 2019 breakthrough: O(nlog⁡n)O(n \log n). David Harvey and Joris van der Hoeven gave an algorithm running in O(nlog⁡n)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.

Where It Matters

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.

Conclusion

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(nlog⁡n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/fast-multiplication/Content licensed under CC BY-NC 4.0.