Karatsuba multiplication

Karatsuba multiplication is a divide-and-conquer algorithm for multiplication of integers. Splitting each operand into two blocks seems to require four smaller products; the Karatsuba three-product identity recovers the two cross terms together from just three products. Repeating that saving through recursion changes the time complexity from quadratic to $O(n^{{\log }_{2}3})$, where $n$ counts digits in a fixed positional notation. The exponent is about $1.585$: the benefit comes from the algorithm, even though each splitting step needs more addition and subtraction.

The Karatsuba worked multiplication below computes $1234\cdot 5678=7,006,652$ using $12\cdot 56$, $34\cdot 78$, and $46\cdot 134$. The last operand already shows why “half-size” needs care: Karatsuba carry handling and Karatsuba recursion termination account for the extra digit. Karatsuba digit-operation cost states the operation model; Karatsuba practical crossover explains why the asymptotic saving alone does not select a useful threshold.

The original 1962 paper presents a binary numeral system automaton construction: its Theorem 2 and proof reduce multiplication to taking squares of numbers, then reduce a larger square of a number to three smaller squares of numbers. Its footnote explicitly addresses the extra digit in a sum of halves. The sequential time complexity analysis below uses a different operation model from that paper's automaton size and depth bounds, including its Boolean circuit realization without feedback.^[ref]

Fix an integer base $B\ge 2$. Let $x,y\ge 0$ have at most $n$ digits in positional notation, treating zero as one digit. For $n>1$, set $m=\lceil n/2\rceil$ using the ceiling function, and $q=B^m$. Euclidean division giveswhere $0\le b,d<q$ and $0\le a,c<B^{n-m}$. The floor function selects the high block; the remainder selects the low block. Both operands must use the same $q$, including when their actual digit lengths differ.

For odd $n$, the low block has $m$ digit positions and the high block has $n-m=m-1$. Leading zero padding aligns a shorter operand without changing its integer value. Padding to a power-of-two length is optional: the split itself works for every $n$. If power-of-two padding is used, the padded length is less than twice the original length, so it changes only a constant factor in the asymptotic analysis.

Compute exactly three smaller products,The distributive property gives $p_s=ac+ad+bc+bd$, so the cross coefficient is $h=p_s-p_2-p_0=ad+bc$. Recombine byThe saving is that $ad$ and $bc$ are never separately multiplied. Multiplying a digit block by $q$ or $q^2$ shifts its position in positional notation; it does not require another general integer multiplication. Addition of the shifted results still requires Karatsuba carry handling.

Use decimal expansion, $B=10$, $n=4$, $m=2$, and $q=100$. The Karatsuba operand splitting is $1234=12\cdot 100+34$, $5678=56\cdot 100+78$. The Karatsuba three-product identity givesThe third product has a three-digit operand. A small-input base case can evaluate these three products directly, or a smaller threshold can continue recursion. Either choice preserves the identity; only the operation count changes.

The same Karatsuba operand splitting handles $123\cdot 45$: choose $n=3$, $m=2$, and write $123=1\cdot 100+23$, $45=0\cdot 100+45$. Then $p_2=0$, $p_0=1035$, $p_s=24\cdot 45=1080$, and $h=45$, giving $4500+1035=5535$. A zero high block and unequal lengths require no new algebraic rule.

The blocks in the Karatsuba three-product identity are integers, not single digits: $p_0$ can need $2m$ positions and $h$ can exceed $q-1$. Concatenating the displayed blocks therefore fails. Accumulate their shifted values with ordinary addition, normalizing each digit position by Euclidean division: a coefficient $v$ becomes the digit $v\mathrm{mod}B$, with carry $\lfloor v/B\rfloor$ passed to the next position. Subtraction likewise propagates borrows. Although $h\ge 0$ for these nonnegative integers, intermediate digitwise subtraction can still borrow.

In the four-digit Karatsuba worked multiplication, grouping by base $q=100$ gives unnormalized coefficients $[672,2840,2652]$, written from high to low. Normalize from the right: $2652=26\cdot 100+52$; $2840+26=2866=28\cdot 100+66$; $672+28=700=7\cdot 100+0$. The final groups are $[7,00,66,52]$, yielding $7,006,652$. The zero group must retain its two positions.

Since $a,b,c,d<B^m$, their sums are less than $2B^m\le B^{m+1}$ and can need $m+1$ digits. Allocate that extra digit before the third recursive product; discarding it can change the answer. The GMP manual describes this sum growth and uses a difference-based form to avoid it.^[ref]

For the sum-based Karatsuba three-product identity, a safe fixed base-case threshold is three digits or more. Return zero directly if either operand is zero; at or below the threshold, use ordinary digit-by-digit multiplication. Otherwise split by the maximum current operand length and invoke Karatsuba multiplication on $(a,c)$, $(b,d)$, and $(a+b,c+d)$.

Each recursive operand has at most $\lceil n/2\rceil +1$ digits. This is strictly less than $n$ for $n\ge 4$, proving termination. A rule stopping only at one digit does not supply this guarantee: in base two, $3=11_2$ splits into $1,1$, whose sum is $2=10_2$, still two digits. An implementation must choose a sufficient threshold or explicitly handle such nonshrinking calls. Leading zero padding must not be repeatedly added in a way that defeats the decreasing size measure.

For signed integers, multiply absolute values with the same nonnegative procedure and restore the sign afterwards. This changes the representation bookkeeping, rather than the three-product identity.

Count a fixed-base digit addition, subtraction, digit copy, or single-digit multiplication as constant cost. Base $B$ stays fixed as $n$ grows; an entire arbitrary-length integer multiplication is not one constant-cost step. With this model, splitting, sum formation, shifts and recombination require $O(n)$ digit operations. Ordinary digit-by-digit multiplication forms $n^2$ digit products for two $n$-position operands. The GMP base-case description uses this rectangular product arrangement.^[ref]

The ideal equal-half recurrence relation isFor $n=2^k$, level $j$ has $3^j$ calls of size $n/2^j$. If each internal call incurs exactly $\alpha$ times its size in additional digit work, that level contributes $\alpha n(3/2{)}^j$. There are $3^k=n^{{\log }_{2}3}$ leaves. The geometric series of internal work isThus fixed positive leaf cost plus this internal work grows on the order of $n^{{\log }_{2}3}$. In Big O notation, $T(n)=O(n^{{\log }_{2}3})$. Removing one of four products at every level matters much more than saving just one at the root.

The literal sum-based implementation instead admits the upper boundfor a nondecreasing worst-case cost envelope above a fixed base-case threshold. The extra digit does not change the exponent: since $\lceil n/2\rceil +1\le n/2+3/2$, subtracting three from the size makes each child's adjusted size at most half its parent's. Stop this comparison at any fixed threshold greater than three; its recursion depth is ${\log }_{2}n+O(1)$ and the level-work sum is bounded by the same geometric series up to constant factors. Exact call counts can depend on carries, zero shortcuts and the threshold, so they need not equal the ideal $3^j$ at each depth.

Karatsuba digit-operation cost explains eventual scaling, while a practical base-case threshold depends on the costs of addition, subtraction, copying and function calls relative to small integer multiplication. Using $M(n)=A{n}^2+Dn+E$ for a base-case cost, one Karatsuba level costs $3M(n/2)+Fn+G$: the quadratic coefficient falls to $3A/4$, but the linear contribution includes $3Dn/2+Fn$. Small operands can therefore cost more despite the smaller exponent. This comparison and the effect of implementation improvements on the threshold are described in the GMP manual.^[ref]

The plotted crossover belongs only to the stipulated constants in its caption; its ordinary-method curve counts digit products alone, while the Karatsuba curve includes the chosen internal overhead. Selecting a threshold for real software requires measuring the actual implementation on its intended machine. With base $B=2^w$ for a fixed machine digit width $w$, the same analysis counts machine digits; it does not establish a universal crossover in decimal digits, bits, or elapsed time.