Karatsuba algorithm

Builds on Algorithm Divide-and-conquer algorithm

Definition

Fix an integer base $B \ge 2$ . The Karatsuba algorithm is the recursive algorithm that computes the product $xy$ of two non-negative integers $x, y$ as follows.

If $x < B$ or $y < B$ , compute $xy$ directly.
Otherwise, let $k \ge 1$ be the least integer with $x, y < B^{2k}$ , and write $x = x_1 B^k + x_0$ and $y = y_1 B^k + y_0$ with $0 \le x_0, y_0 < B^k$ .
Compute recursively $z_2 = x_1 y_1$ , $z_0 = x_0 y_0$ and $z_3 = (x_1 + x_0)(y_1 + y_0)$ .
Return $z_2 B^{2k} + (z_3 - z_2 - z_0) B^k + z_0$ .

The output is correct because $z_3 - z_2 - z_0 = x_1 y_0 + x_0 y_1$ , so the returned number equals $(x_1 B^k + x_0)(y_1 B^k + y_0)$ .

Remarks

Example: with $B = 10$ , $x = 12$ , $y = 34$ and $k = 1$ , one gets $z_2 = 3$ , $z_0 = 8$ and $z_3 = 3 \cdot 7 = 21$ . The result is $3 \cdot 100 + (21 - 3 - 8) \cdot 10 + 8 = 408 = 12 \cdot 34$ .

Non-example: computing the four products $x_1 y_1$ , $x_1 y_0$ , $x_0 y_1$ , $x_0 y_0$ recursively is also correct, but it is not the Karatsuba algorithm. Its cost satisfies $T(n) = 4 T(n/2) + O(n)$ , which gives only $O(n^2)$ .

For $n$ -digit inputs with $k$ about $n/2$ , the cost of the Karatsuba algorithm satisfies $T(n) = 3 T(n/2) + O(n)$ . By the master theorem, $T(n) = O(n^{\log_2 3})$ in asymptotic notation.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`EHH9KQHYFA`
URI	`m2://EHH9KQHYFA`
Kind	definition
Writing	W0 stub
MSC	68W30, 68W40, 11Y16
Defines	Karatsuba algorithm
Uses	Algorithm, Divide-and-conquer algorithm
Changed	3 November 2026

Karatsuba algorithm

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here