---
title: Fast Multiplication
module: Divide & Conquer
moduleNumber: 2
lessonNumber: 4
order: 204
summary: |
  Grade-school multiplication is $\Theta(n^2)$, yet divide and conquer beats it.
  Karatsuba multiplies $n$-bit integers with three half-size products instead of
  four, giving $\Theta(n^{\log_2 3})$, and Strassen multiplies matrices with
  seven block products instead of eight, giving $\Theta(n^{\log_2 7})$. Both
  spend cheap additions to save an expensive multiplication, and the master
  theorem quantifies the savings.
topics: [Divide & Conquer, Arithmetic]
sources:
  - book: CLRS
    ref: "Ch. 4 — Divide-and-Conquer (Strassen, §4.2)"
  - book: Erickson
    ref: "Ch. 1 — Recursion"
  - book: Skiena
    ref: "§13 — Numerical Problems"
practice:
  - title: 'Multiply Strings'
    slug: multiply-strings
    difficulty: Medium
  - title: 'Add Two Numbers'
    slug: add-two-numbers
    difficulty: Medium
  - title: 'Plus One'
    slug: plus-one
    difficulty: Easy
  - title: 'Pow(x, n)'
    slug: powx-n
    difficulty: Medium
---

Adding two $n$-bit numbers is easy: the grade-school ripple-carry method is
$\Theta(n)$, and you cannot beat linear because you must at least read the
input. **Multiplication** is the interesting one. The grade-school algorithm
forms $n$ shifted partial products and sums them, costing $\Theta(n^2)$. For a
long time that was assumed to be the best possible — until divide and conquer
showed otherwise. The same idea then breaks the cubic bound for **matrix
multiplication**. Both stories share a single idea: _spend a few cheap
additions to buy back one expensive multiplication._[^clrs-dc]

## Multiplying integers: the schoolbook baseline

Write each $n$-bit integer as a high half and a low half. With $n = 2t$, split
$x$ into its least-significant $t$ bits $a$ and its top $t$ bits $b$, and
likewise split $y$ into $c$ and $d$:

$$
% caption: Splitting each $n$-bit integer $x$ and $y$ into high and low $t$-bit halves, so
%          $x = a + 2^{t} b$ and $y = c + 2^{t} d$.
\begin{tikzpicture}[font=\small, >={Stealth[round]},
  half/.style={draw, minimum width=24mm, minimum height=8mm, inner xsep=6pt, outer sep=0}]
  \definecolor{acc}{HTML}{2348F2}
  % x
  \node at (-1.4,0.4) {$x =$};
  \node[half, anchor=west] (xb) at (0,0.4) {$b$ (high $t$ bits)};
  \node[half, anchor=west] (xa) at (xb.east) {$a$ (low $t$ bits)};
  % y
  \node at (-1.4,-1.0) {$y =$};
  \node[half, anchor=west] (yd) at (0,-1.0) {$d$ (high $t$ bits)};
  \node[half, anchor=west] (yc) at (yd.east) {$c$ (low $t$ bits)};
  \node[font=\scriptsize\itshape, anchor=west] at ($(xa.east)+(8mm,0)$) {$x = a + 2^{t} b$};
  \node[font=\scriptsize\itshape, anchor=west] at ($(yc.east)+(8mm,0)$) {$y = c + 2^{t} d$};
\end{tikzpicture}
$$

Multiplying out $x = a + 2^t b$ and $y = c + 2^t d$ gives

$$
xy = ac + 2^{t}(ad + bc) + 2^{2t}\,bd .
$$

$$
% caption: The naive split forms all four cross-products of the halves
%          $\{a, b\} \times \{c, d\}$: the diagonal terms $ac$ and $bd$ become the low and
%          high coefficients, while $ad$ and $bc$ both feed the middle coefficient
%          $2^{t}(ad + bc)$. Four half-size multiplications in all.
\begin{tikzpicture}[font=\small, x=1cm, y=1cm,
  cell/.style={draw, minimum width=16mm, minimum height=10mm}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-1.6,-3.0) rectangle (5.4,1.0);
  % column headers (factors of y)
  \node at (0.0,0.55) {$c$};
  \node at (1.6,0.55) {$d$};
  % row headers (factors of x)
  \node at (-1.0,-0.5) {$a$};
  \node at (-1.0,-1.7) {$b$};
  % the four products
  \node[cell, fill=black!8] at (0.0,-0.5) {$ac$};
  \node[cell, fill=acc!12] at (1.6,-0.5) {$ad$};
  \node[cell, fill=acc!12] at (0.0,-1.7) {$bc$};
  \node[cell, fill=black!8] at (1.6,-1.7) {$bd$};
  % role labels (plain words; precise terms live in the caption)
  \node[font=\scriptsize, anchor=north west] at (-1.5,-2.6) {solid corners give the low and high terms};
  \node[font=\scriptsize, acc, anchor=north west] at (-1.5,-3.05) {light pair gives the middle term};
\end{tikzpicture}
$$

The powers of two are just bit-shifts (free, up to the additions), so the cost
is dominated by the **four** half-size products $ac$, $ad$, $bc$, $bd$. That
yields a recurrence

$$
T(n) \le 4\,T(n/2) + \Theta(n).
$$

Unrolling it shows this naïve split buys nothing:

$$
\begin{aligned}
T(n) &\le 4\,T(n/2) + bn \le 4\parens{4\,T(n/4) + b\tfrac n2} + bn
   = 16\,T(n/4) + 2bn + bn \\
&\le \cdots \le 4^{i}\,T(n/2^{i}) + \underbrace{\parens{bn + 2bn + \cdots +
   2^{\,i-1}bn}}_{(2^{i}-1)\,bn} .
\end{aligned}
$$

At $i = \log_2 n$ the leaf term is $4^{\log_2 n}\,T(1) = n^{2}\,T(1)$, which
dominates everything: $T(n) = \Theta(n^2)$. The [master
theorem](/algorithms/foundations/recurrences) says the same instantly: with
$a = 4$, $b = 2$, $c = 1$, the branching exponent $\log_2 4 = 2$ exceeds the
work exponent $1$, so the recurrence is **leaf-heavy** and
$T(n) = \Theta(n^{\log_2 4}) = \Theta(n^2)$. Four subproblems of half size land
us right back in the quadratic regime.

::impl{algo="karatsuba#schoolbook_multiply"}

## Karatsuba: three products instead of four

The fix, due to Karatsuba (1960), is to compute the middle coefficient
$ad + bc$ _without_ a third and fourth multiplication.[^karatsuba] Notice the
algebraic identity

$$
(a - b)(d - c) = ad - ac - bd + bc,
\qquad\text{so}\qquad
ad + bc = (a - b)(d - c) + ac + bd .
$$

We were going to compute $ac$ and $bd$ anyway. So once we have those two
products, the middle term needs only **one** more multiplication,
$(a - b)(d - c)$, plus a few additions. Three half-size products now suffice
where four were needed.

$$
% caption: Karatsuba reuses the products $ac$ and $bd$ to recover the middle coefficient
%          $ad+bc = (a-b)(d-c) + ac + bd$ from a single extra product $(a-b)(d-c)$ (the
%          solid blue box), replacing the naive four products with three.
\begin{tikzpicture}[font=\scriptsize, >={Stealth[round]}, x=1cm, y=1cm,
  box/.style={draw, minimum width=18mm, minimum height=7mm, inner sep=2pt}]
  \definecolor{acc}{HTML}{2348F2}
  % the three products (left column)
  \node[box] (p1) at (0,0) {\texttt{product} $ac$};
  \node[box] (p2) at (0,-1.2) {\texttt{product} $bd$};
  \node[box, fill=acc!30, draw=acc, line width=0.8pt, minimum width=24mm] (p3) at (0.3,-2.4) {\texttt{extra product}};
  \node[font=\footnotesize, anchor=east] at (-1.05,-0.6) {\texttt{reused}};
  \node[font=\footnotesize, anchor=east, acc] at (-1.05,-2.4) {\texttt{the trick}};
  % the three output coefficients (right column): neutral, outlined in black
  \node[box, fill=black!4, draw=black] (lo)  at (5.0, 0.0) {low term};
  \node[box, fill=black!4, draw=black] (mid) at (5.0,-1.2) {middle term};
  \node[box, fill=black!4, draw=black] (hi)  at (5.0,-2.4) {high term};
  % wiring
  \draw[->]    (p1.east) -- (lo.west);
  \draw[->]    (p2.east) -- (hi.west);
  \draw[->, acc, line width=0.9pt] (p3.east) -- (mid.west);
  \draw[->, dashed] (p1.east) to[out=-25,in=160] (mid.west);
  \draw[->, dashed] (p2.east) to[out=25,in=200]  (mid.west);
\end{tikzpicture}
$$

The low and high coefficients are just $ac$ and $bd$; the middle coefficient
$ad + bc$ is recovered from the single extra product $(a-b)(d-c)$ plus the two
reused products, as $(a-b)(d-c) + ac + bd$.

```algorithm
caption: $\textsc{Karatsuba}(x, y)$ — multiply two $n$-bit integers
number: 1
if $n = 1$ then
  return $x \cdot y$ // base case: one-bit (or word) product
$t \gets \floor{n / 2}$
split $x = a + 2^{t} b$ and $y = c + 2^{t} d$ // low and high halves
$\mathit{ac} \gets \textsc{Karatsuba}(a, c)$ // recursive product 1
$\mathit{bd} \gets \textsc{Karatsuba}(b, d)$ // recursive product 2
$m \gets \textsc{Karatsuba}(a - b, d - c)$ // recursive product 3 — the trick
$\mathit{mid} \gets m + \mathit{ac} + \mathit{bd}$ // recovers $ad + bc$
return $\mathit{ac} + 2^{t}\,\mathit{mid} + 2^{2t}\,\mathit{bd}$ // shift and add
```

::impl{algo="karatsuba#karatsuba"}

> **Claim (Correctness).** $\textsc{Karatsuba}(x, y)$ returns $x \cdot y$.

> **Proof.** By the identity above, $\mathit{mid} = m + ac + bd = (a-b)(d-c) +
> ac + bd = ad + bc$, so the returned value is $ac + 2^{t}(ad + bc) + 2^{2t}bd$,
> which expands $(a + 2^t b)(c + 2^t d) = xy$. The base case
> $n = 1$ is a direct product. Correctness then follows by induction on $n$,
> trusting the three recursive calls to multiply their half-size operands.
> $\qed$

### A worked example in base 10

The identity is base-agnostic, so it is easiest to watch on ordinary decimal
digits. Multiply $x = 1234$ by $y = 5678$. Split each at the middle two digits,
using $10^{2}$ as the base (so $t$ counts _digits_ here, not bits):

$$
x = \underbrace{12}_{b}\cdot 10^{2} + \underbrace{34}_{a},
\qquad
y = \underbrace{56}_{d}\cdot 10^{2} + \underbrace{78}_{c}.
$$

Karatsuba needs three products of the two-digit halves:

$$
\begin{aligned}
ac &= 34 \cdot 78 = 2652, \\
bd &= 12 \cdot 56 = 672, \\
(a-b)(d-c) &= (34-12)(56-78) = 22 \cdot (-22) = -484.
\end{aligned}
$$

The middle coefficient falls out of the identity with no further multiplication:

$$
\mathit{mid} = (a-b)(d-c) + ac + bd = -484 + 2652 + 672 = 2840.
$$

Reassemble by shifting each coefficient to its place value and adding:

$$
xy = ac + \mathit{mid}\cdot 10^{2} + bd\cdot 10^{4}
   = 2652 + 2840\cdot 10^{2} + 672\cdot 10^{4}.
$$

$$
% caption: Karatsuba on $1234 \times 5678$ in base $10$. Three two-digit products feed the
%          low, middle, and high coefficients; each is shifted to its place value and
%          summed to give $7\,006\,652$.
\begin{tikzpicture}[font=\footnotesize, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  % the three coefficient rows, shifted by place value (each column = 4 digit widths)
  \node[anchor=east] at (0,0)     {\texttt{ac       =}};
  \node[anchor=east] at (0,-0.65) {\texttt{mid . 100 =}};
  \node[anchor=east] at (0,-1.3)  {\texttt{bd . 10000 =}};
  % right-aligned digit strings (monospace keeps columns)
  \node[anchor=east] at (5.0,0)     {\texttt{2652}};
  \node[anchor=east] at (5.0,-0.65) {\texttt{284000}};
  \node[anchor=east] at (5.0,-1.3)  {\texttt{6720000}};
  \draw (1.2,-1.62) -- (5.05,-1.62);
  \node[anchor=east] at (0,-2.0)  {\texttt{xy       =}};
  \node[anchor=east, acc, font=\bfseries] at (5.0,-2.0) {\texttt{7006652}};
\end{tikzpicture}
$$

A cross-check confirms it: $1234 \times 5678 = 7{,}006{,}652$. The schoolbook
method would have formed four two-digit products ($34\cdot78$, $34\cdot56$,
$12\cdot78$, $12\cdot56$); Karatsuba used three and recovered the fourth's
contribution from a subtraction.

### Cost

There are now $a = 3$ recursive calls, each on half-size inputs, with
$\Theta(n)$ work to split, shift, and add (the subtractions $a - b$, $d - c$ may
produce one extra bit, which does not change the asymptotics):

$$
T(n) = 3\,T(n/2) + \Theta(n).
$$

The recursion tree makes the cost legible. Level $i$ has $3^{i}$ nodes, each
doing $bn/2^{i}$ work, for a row total of $(3/2)^{i}\,bn$. The rows _grow_
geometrically downward, so the leaves dominate:

$$
% caption: Each Karatsuba node spawns $3$ half-size children, so the rows grow by $3/2$
%          downward and the $\Theta(n^{\log_2 3})$ leaf level dominates the cost.
\begin{tikzpicture}[font=\scriptsize, >={Stealth[round]}, level distance=12mm,
  level 1/.style={sibling distance=26mm},
  level 2/.style={sibling distance=8.5mm}]
  \definecolor{acc}{HTML}{2348F2}
  \tikzstyle{every node}=[draw, circle, inner sep=1.6pt, minimum size=4.5mm]
  \tikzstyle{lf}=[draw, circle, fill=acc!30, minimum size=2.6mm, inner sep=0pt]
  \node {$n$}
    child {node {$\tfrac n2$} child {node[lf]{}} child {node[lf]{}} child {node[lf]{}}}
    child {node {$\tfrac n2$} child {node[lf]{}} child {node[lf]{}} child {node[lf]{}}}
    child {node {$\tfrac n2$} child {node[lf]{}} child {node[lf]{}} child {node[lf]{}}};
\end{tikzpicture}
$$

Summing the geometric row totals,

$$
T(n) \le bn\sum_{i=0}^{\log_2 n} \parens{\tfrac32}^{i}
   = \Theta\!\parens{\parens{\tfrac32}^{\log_2 n}} \cdot bn
   = \Theta\!\parens{n^{\log_2 3}} \approx \Theta(n^{1.585}),
$$

using $n^{\log_2 3} = (3/2)^{\log_2 n}\cdot n$ (the identity
$x^{\log_a y} = y^{\log_a x}$). The [master
theorem](/algorithms/foundations/recurrences) confirms it in one line: with
$a = 3$, $b = 2$, $c = 1$, the branching exponent $\log_2 3 \approx 1.585$
beats the work exponent $1$, so this is **leaf-heavy** and
$T(n) = \Theta(n^{\log_2 3})$. Trading one multiplication for a handful of
additions drops integer multiplication below quadratic.

> **Remark (Why it matters).** The win is purely asymptotic: each level does the
> same kind of work, but there are _fewer_ subproblems than the naive split, so
> the tree is shallower at the leaves. The _number_ of subproblems, not their
> size, drives the exponent — exactly what the master theorem captures.

## Strassen: seven products instead of eight

The same "spend additions to save a multiplication" idea breaks the cubic
bound for **matrix multiplication**. The schoolbook method costs $\Theta(n^3)$:
each of the $n^2$ entries of $C = AB$ is a length-$n$ dot product. Divide and
conquer splits each $n \times n$ matrix into four $(n/2) \times (n/2)$ blocks,
and the product is read off block by block exactly as for $2 \times 2$ scalars:

$$
A = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix},\quad
B = \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix},\quad
C = \begin{pmatrix}
A_{11}B_{11}+A_{12}B_{21} & A_{11}B_{12}+A_{12}B_{22} \\
A_{21}B_{11}+A_{22}B_{21} & A_{21}B_{12}+A_{22}B_{22}
\end{pmatrix}.
$$

$$
% caption: Each $n \times n$ matrix splits into four $(n/2) \times (n/2)$ blocks. Naively,
%          every output block $C_{ij} = A_{i1}B_{1j} + A_{i2}B_{2j}$ is a sum of two block
%          products, so the four outputs cost eight half-size multiplications.
\begin{tikzpicture}[font=\small, x=1cm, y=1cm,
  blk/.style={draw, minimum size=11mm}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.6,-2.2) rectangle (11.4,1.7);
  % A
  \node[font=\footnotesize, anchor=south] at (0.55,1.25) {$A$};
  \node[blk] at (0,0.55)  {$A_{11}$};
  \node[blk] at (1.1,0.55) {$A_{12}$};
  \node[blk] at (0,-0.55) {$A_{21}$};
  \node[blk] at (1.1,-0.55) {$A_{22}$};
  % times
  \node at (2.1,0) {times};
  % B
  \node[font=\footnotesize, anchor=south] at (3.65,1.25) {$B$};
  \node[blk] at (3.1,0.55)  {$B_{11}$};
  \node[blk] at (4.2,0.55) {$B_{12}$};
  \node[blk] at (3.1,-0.55) {$B_{21}$};
  \node[blk] at (4.2,-0.55) {$B_{22}$};
  % equals
  \node at (5.2,0) {gives};
  % C
  \node[font=\footnotesize, anchor=south] at (6.85,1.25) {$C$};
  \node[blk, fill=acc!15] at (6.3,0.55)  {$C_{11}$};
  \node[blk, fill=acc!15] at (7.4,0.55) {$C_{12}$};
  \node[blk, fill=acc!15] at (6.3,-0.55) {$C_{21}$};
  \node[blk, fill=acc!15] at (7.4,-0.55) {$C_{22}$};
  % annotation
  \node[font=\footnotesize, acc, anchor=west, align=left] at (8.2,0) {\texttt{each block:}\\\texttt{two products}};
\end{tikzpicture}
$$

Taken at face value, the four output blocks need **eight** block multiplications,
giving $T(n) = 8\,T(n/2) + \Theta(n^2)$. The master theorem returns
$\Theta(n^{\log_2 8}) = \Theta(n^3)$: more subproblems exactly cancel their
smaller size, so blocking alone buys nothing — the integer-multiplication story
again, one dimension up.

Strassen's 1969 insight is that **seven** products suffice.[^strassen] Form seven
recursive $(n/2)$-size multiplications,

$$
\begin{aligned}
M_1 &= (A_{11}+A_{22})(B_{11}+B_{22}), & M_5 &= (A_{11}+A_{12})\,B_{22}, \\
M_2 &= (A_{21}+A_{22})\,B_{11},        & M_6 &= (A_{21}-A_{11})(B_{11}+B_{12}), \\
M_3 &= A_{11}\,(B_{12}-B_{22}),        & M_7 &= (A_{12}-A_{22})(B_{21}+B_{22}), \\
M_4 &= A_{22}\,(B_{21}-B_{11}),        &     &
\end{aligned}
$$

and recover the output blocks by **addition only**:

$$
\begin{aligned}
C_{11} &= M_1+M_4-M_5+M_7, & C_{12} &= M_3+M_5, \\
C_{21} &= M_2+M_4,        & C_{22} &= M_1-M_2+M_3+M_6.
\end{aligned}
$$

The eighth multiplication is gone, traded for a handful of extra block additions
that cost only $\Theta(n^2)$. The recurrence becomes

$$
T(n) = 7\,T(n/2) + \Theta(n^2),
$$

and now the leaves win. With $a = 7$, $b = 2$, $c = 2$, the branching exponent
$\log_2 7 \approx 2.807$ exceeds the work exponent $2$, so by the master theorem

$$
T(n) = \Theta\!\parens{n^{\log_2 7}} \approx \Theta\!\parens{n^{2.807}}.
$$

$$
% caption: Naive blocking fans out into $8$ half-size products (root-heavy ties at
%          $\Theta(n^3)$); Strassen drops one to $7$, and the smaller fan-out — not the
%          block size — pulls the exponent down to $\log_2 7 \approx 2.807$.
\begin{tikzpicture}[font=\scriptsize, >={Stealth[round]}, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  % naive: 8 children (light blue, outlined)
  \node[draw, circle, minimum size=7mm] (r8) at (0,1.6) {$n$};
  \foreach \i in {0,...,7} {
    \node[draw, circle, minimum size=5mm] (a\i) at ({(\i-3.5)*0.62},0) {};
    \draw[->] (r8) -- (a\i);
  }
  \node[font=\footnotesize, anchor=north] at (0,-0.45) {\texttt{naive: 8 products}};
  \node[font=\scriptsize, anchor=north] at (0,-0.95) {cost $n^3$};
  % strassen: 7 children (solid blue, the winning fan-out)
  \node[draw=acc, circle, fill=acc!30, minimum size=7mm] (r7) at (6.6,1.6) {$n$};
  \foreach \i in {0,...,6} {
    \node[draw=acc, circle, fill=acc!30, minimum size=5mm] (b\i) at ({6.6+(\i-3)*0.62},0) {};
    \draw[->, acc] (r7) -- (b\i);
  }
  \node[font=\footnotesize, anchor=north, acc] at (6.6,-0.45) {\texttt{Strassen: 7 products}};
  \node[font=\scriptsize, anchor=north, acc] at (6.6,-0.95) {cost $n^{\log_2 7}$};
\end{tikzpicture}
$$

The constant is large, so the crossover with the cubic method only pays off for
sizable $n$; in practice Strassen is switched in above a threshold and the base
case falls back to the cache-friendly schoolbook multiply. Theoretically,
though, it was the **first sub-cubic algorithm**, and a long line of
refinements has pushed the exponent down toward $2.37$.

::impl{algo="strassen"}

## Crossover: when divide and conquer actually wins

Both algorithms carry a fat constant: Karatsuba does extra additions and
subtractions, Strassen does $18$ block additions per level versus the naive
$8$ products' simpler bookkeeping. Below some threshold $n_0$ the schoolbook
method's smaller constant wins outright, so every real implementation switches
**back** to schoolbook at the base case rather than recursing down to $n = 1$.

$$
% caption: The fast method has a better exponent but a fatter constant, so its cost curve
%          starts above schoolbook and crosses it only at a threshold $n_0$. Below $n_0$
%          schoolbook is cheaper (left of the dashed line); above it the fast method wins.
%          Libraries switch over only past the crossover.
\begin{tikzpicture}[
  >={Stealth[length=2.4mm]},
  lbl/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.8,-1.2) rectangle (9.6,4.4);
  % axes
  \draw[->] (0,0) -- (9.4,0) node[lbl, right] {input size $n$};
  \draw[->] (0,0) -- (0,4.2) node[lbl, above] {cost};
  % schoolbook: steeper at large n (light blue)
  \draw[line width=1.6pt]
    (0.2,0.1) .. controls (4,0.9) and (6,2.4) .. (8.6,4.0);
  \node[lbl, anchor=south east] at (8.5,4.0) {\texttt{schoolbook}};
  % fast method: higher constant, gentler growth (solid blue)
  \draw[acc, line width=1.6pt]
    (0.2,1.0) .. controls (3,1.6) and (6,2.4) .. (8.6,3.1);
  \node[lbl, acc, anchor=south west] at (7.0,3.15) {\texttt{fast method}};
  % crossover marker
  \draw[densely dashed, black, line width=0.8pt] (5.55,0) -- (5.55,2.25);
  \fill[black] (5.55,2.25) circle (1.4pt);
  \node[lbl, anchor=north] at (5.55,-0.1) {$n_0$};
  \node[lbl, black!70, anchor=north east] at (5.3,-0.05) {\texttt{schoolbook cheaper}};
  \node[lbl, black!70, anchor=north west] at (5.8,-0.05) {\texttt{fast cheaper}};
\end{tikzpicture}
$$

> **Note (Practical recursion).** Production big-integer libraries (GMP, Java's
> `BigInteger`) keep a tower of algorithms: schoolbook for tiny operands,
> Karatsuba in the middle, Toom–Cook and then FFT-based multiplication for the
> very large. Each is fastest in its own size band, and the library picks by
> operand length. The same pattern holds for matrices: schoolbook below a tuned
> $n_0$, Strassen above it.

This is the recurring theme of asymptotically fast algorithms — a better
exponent is worthless until $n$ is large enough to overcome the constant, so the
clever method is layered _on top of_ a simple base case, not used in place of it.

## Toom–Cook: splitting into more pieces

Karatsuba splits each operand into two halves and uses three products. The same
idea generalizes. View an $n$-digit integer written in base $B = 10^{n/k}$ as a
degree-$(k-1)$ **polynomial** whose coefficients are the $k$ chunks:
$x = \sum_{i} x_i B^{i}$ is the polynomial $X(z) = \sum_i x_i z^{i}$ evaluated at
$z = B$. Multiplying the integers is multiplying the polynomials and then
substituting $z = B$ (a shift-and-add that resolves carries).

The product $X(z)Y(z)$ has degree $2k-2$, so it is determined by its values at
$2k-1$ points. **Toom–Cook** (specifically Toom-$k$) runs three phases:

- **evaluate** $X$ and $Y$ at $2k-1$ small points (e.g. $0, \pm1, \pm2, \dots$),
- **multiply** the paired values pointwise — $2k-1$ recursive products of
  $\approx n/k$-size numbers,
- **interpolate** the $2k-1$ products back into the coefficients of $X(z)Y(z)$,
  then evaluate at $z = B$.

Karatsuba _is_ Toom-$2$: two chunks, $2\cdot2-1 = 3$ products. Toom-$3$
uses three chunks and $5$ products of third-size operands, giving
$T(n) = 5\,T(n/3) + \Theta(n) = \Theta(n^{\log_3 5}) \approx \Theta(n^{1.465})$ —
a better exponent than Karatsuba's $1.585$, at the price of a messier
interpolation step with larger additive constants. In general Toom-$k$ achieves
$\Theta(n^{\log_k(2k-1)})$, and as $k$ grows the exponent creeps toward $1$ — but
the evaluate/interpolate overhead grows too, so no fixed $k$ reaches
near-linear.

## FFT multiplication: near-linear

The **Fast Fourier Transform** takes the polynomial view to its conclusion.
Instead of a fixed handful of evaluation points, evaluate at the $2n$ complex
$2n$-th roots of unity. The FFT performs that evaluation for _all_ roots at once
in $\Theta(n\log n)$ (a divide-and-conquer that splits a polynomial into its
even- and odd-indexed coefficients), the pointwise multiply is $\Theta(n)$, and
the inverse FFT interpolates back in another $\Theta(n\log n)$. Substituting
$z = B$ and resolving carries finishes the integer product. The total is

$$
T(n) = \Theta(n\log n)
$$

for the polynomial multiply, and $\Theta(n\log n\log\log n)$ for integer
multiplication once one accounts for the growing precision of the roots
(Schönhage–Strassen). A 2019 result of Harvey and van der Hoeven removed the last
$\log\log n$ factor, reaching $\Theta(n\log n)$ — conjectured to be optimal.

The through-line is one substitution: multiplying two integers _is_ multiplying
two polynomials in the base variable, then carrying. Every method here — the
schoolbook grid, Karatsuba, Toom–Cook, FFT — is a different way to multiply
those polynomials, trading more evaluation-and-interpolation bookkeeping for
fewer recursive products. Fast multiplication therefore leads directly to fast
polynomial arithmetic, and shows up wherever big integers or high-degree
polynomials do: cryptography, computer algebra, and signal processing among
them.[^skiena-num]

$$
% caption: The exponent ladder for integer multiplication. Splitting into more chunks and
%          reusing products drops the exponent from $2$ (schoolbook) toward $1$ (FFT); each
%          rung trades heavier evaluate/interpolate overhead for fewer recursive products.
\begin{tikzpicture}[font=\footnotesize, >=Stealth, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  % a horizontal exponent axis from 1 to 2
  \draw[->] (0,0) -- (9.4,0) node[anchor=west, font=\footnotesize] {\texttt{exponent}};
  \foreach \p/\lab in {0/1, 3/1.46, 4.3/1.58, 8.6/2} {
    \draw (\p,0.08) -- (\p,-0.08);
    \node[anchor=north, font=\scriptsize] at (\p,-0.1) {\lab};
  }
  % method markers above the axis, staggered to avoid label collisions
  \node[draw, font=\footnotesize, anchor=south] at (8.6,0.25) {\texttt{schoolbook}};
  \node[draw, font=\footnotesize, anchor=south] at (4.3,1.0) {\texttt{Karatsuba}};
  \draw[thin] (4.3,0.95) -- (4.3,0.1);
  \node[draw, font=\footnotesize, anchor=south] at (3.0,0.25) {\texttt{Toom-3}};
  \node[draw=acc, fill=acc!30, font=\footnotesize, anchor=south] at (0,0.25) {\texttt{FFT}};
\end{tikzpicture}
$$

## Frontiers of multiplication

The two stories in this lesson — integer and matrix multiplication — both remain
open at their frontiers, and both illustrate a gap between what is _asymptotically_
fastest and what any machine will ever run.

**Integer multiplication: the conjectured floor was reached.** For decades the
best known bound was Schönhage–Strassen's $\Theta(n\log n\log\log n)$ (1971), the
FFT method of the previous section. It was long conjectured that $\Theta(n\log n)$
is the true complexity, with no room below. In **2019 Harvey and van der Hoeven**
proved exactly that bound: an algorithm multiplying $n$-bit integers in
$O(n\log n)$. It is a landmark — it likely closes the problem — but it is a
**galactic algorithm**: the constant hidden in the $O$ is so enormous (the method
lifts the numbers into a high-dimensional FFT over a cleverly chosen ring) that
the crossover where it beats Schönhage–Strassen exceeds any input that will ever
be multiplied. It settles the theory while changing nothing in practice, where the
tower of schoolbook, Karatsuba, Toom–Cook, and Schönhage–Strassen from earlier
still governs which method a library picks by operand size.

**Matrix multiplication: a moving target.** Strassen's $\Theta(n^{\log_2 7})
\approx \Theta(n^{2.807})$ opened a race that is still running. Let $\omega$ be the
**matrix-multiplication exponent** — the smallest number such that
$n\times n$ matrices can be multiplied in $O(n^{\omega+\varepsilon})$ for every
$\varepsilon > 0$. Strassen put $\omega \le 2.807$; the **Coppersmith–Winograd**
algorithm (1990) and its laser-method descendants (Williams 2012, and Alman &
Williams 2021) have pushed the record to $\omega < 2.372$. Every one of these is
galactic — the constants make them useless below astronomically large $n$ — so
practical libraries still use Strassen above a tuned threshold and schoolbook
below it. The lower bound is only the trivial $\omega \ge 2$ (you must at least
read the $n^2$ inputs), and whether $\omega = 2$ is one of the central open
questions of algorithm theory.

$$
% caption: The matrix-multiplication exponent $\omega$ over time. Strassen's $2.807$ began a
%          descent toward the trivial floor $\omega \ge 2$; every improvement past Strassen
%          is galactic (useless at practical sizes), and whether $\omega = 2$ is open.
\begin{tikzpicture}[font=\footnotesize, >=Stealth, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->] (0,0) -- (7.4,0) node[anchor=west, font=\scriptsize] {\texttt{exponent}};
  \foreach \p/\lab in {0/2.0, 2.4/2.37, 4.6/2.81, 7/3.0} {
    \draw (\p,0.08) -- (\p,-0.08);
    \node[anchor=north, font=\scriptsize] at (\p,-0.1) {\lab};
  }
  \node[draw, font=\footnotesize, anchor=south] at (7,0.25) {\texttt{schoolbook}};
  \node[draw, font=\footnotesize, anchor=south] at (4.6,0.25) {\texttt{Strassen}};
  \node[draw=acc, fill=acc!12, font=\footnotesize, anchor=south] at (2.4,1.0) {\texttt{Alman-Williams}};
  \draw[acc, thin] (2.4,0.95) -- (2.4,0.1);
  \node[draw=black, fill=black!6, font=\footnotesize, anchor=south] at (0,0.25) {\texttt{floor: read inputs}};
\end{tikzpicture}
$$

**When the algebra is discovered by search.** Strassen found his seven products by
hand; the modern twist is to let a machine search for such identities.
**AlphaTensor** (Fawzi et al., 2022) cast the discovery of low-rank matrix
multiplication schemes as a single-player game and, with reinforcement learning,
rediscovered Strassen-like decompositions and found new ones for specific small
sizes (for instance a $4\times 4$ scheme over $\mathbb{Z}_2$ using fewer
multiplications than the previously known best). It is the same idea this lesson
turns on — trade multiplications for additions — but with the search for _which_
additions automated rather than reasoned out. The frontier of "spend cheap
operations to save expensive ones" is now partly a search problem.

## Takeaways

- **Schoolbook** integer multiplication is $\Theta(n^2)$; the naive divide split
  into four half-size products, $T(n) = 4T(n/2) + \Theta(n)$, stays $\Theta(n^2)$.
- **Karatsuba** uses the identity $ad + bc = (a-b)(d-c) + ac + bd$ to compute the
  middle coefficient from one extra product, cutting four subproblems to three:
  $T(n) = 3T(n/2) + \Theta(n) = \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$.
- **Schoolbook** matrix multiplication is $\Theta(n^3)$; naive block divide,
  $T(n) = 8T(n/2) + \Theta(n^2)$, stays $\Theta(n^3)$.
- **Strassen** recovers the four output blocks from seven products instead of
  eight: $T(n) = 7T(n/2) + \Theta(n^2) = \Theta(n^{\log_2 7}) \approx
  \Theta(n^{2.807})$ — the first sub-cubic matrix multiply.
- The [master theorem](/algorithms/foundations/recurrences) reads off every one
  of these by comparing the branching exponent $\log_b a$ to the work exponent
  $c$; both fast methods are **leaf-heavy**.
- **Toom–Cook** generalizes Karatsuba by splitting into $k$ chunks and treating
  the digits as polynomial coefficients: Toom-$k$ uses $2k-1$ products for
  $\Theta(n^{\log_k(2k-1)})$; Karatsuba is Toom-$2$.
- The **FFT** evaluates at roots of unity to multiply the underlying polynomials
  in $\Theta(n\log n)$, giving near-linear integer multiplication (down to
  $\Theta(n\log n)$ since 2019).
- Both win only asymptotically: a fat constant means the clever method is layered
  above a schoolbook base case, switched in only past a crossover size $n_0$.
- At the frontier both problems are open or **galactic**: Harvey–van der Hoeven
  (2019) reached the conjectured $\Theta(n\log n)$ for integers, and the
  matrix-multiplication exponent has fallen to $\omega < 2.372$ (Alman–Williams)
  with the trivial $\omega \ge 2$ the only known floor — all useless at real
  sizes, and now partly discovered by machine search (AlphaTensor).

[^clrs-dc]: **CLRS**, Ch. 4 — Divide-and-Conquer: integer and matrix multiplication as divide-and-conquer case studies, trading multiplications for additions.
[^karatsuba]: **Erickson**, _Algorithms_, Ch. 1 — Recursion: Karatsuba's $n$-bit integer multiplication via the identity reducing four half-size products to three, with the $T(n) = 3T(n/2) + O(n) = O(n^{\log_2 3})$ recurrence.
[^strassen]: **CLRS**, Ch. 4 (§4.2) — Strassen's algorithm for matrix multiplication and its $\Theta(n^{\log_2 7})$ recurrence; the original result is V. Strassen (1969), "Gaussian elimination is not optimal," _Numerische Mathematik_ 13, 354–356.
[^skiena-num]: **Skiena**, _The Algorithm Design Manual_, §13 — Numerical Problems: high-precision arithmetic, the link from integer to polynomial multiplication, and FFT-based methods for large operands.