Motivation
Splitting two numbers into high and low halves seems to require four smaller multiplications: high by high, high by low, low by high, and low by low. Karatsuba's observation recovers the sum of the two cross products from one additional multiplication. Three recursive products instead of four change the asymptotic exponent.
The arithmetic identity is short, but a careful complexity proof must account for carries in the sums and for uneven input lengths. We analyze a deliberately padded implementation so that its recursion is well defined for every digit length and its operation count does not depend on whether leading digits happen to vanish.
Digits and the three products
Definition 1.6.1
(Splitting and the three products)
Fix a radix . Consider nonnegative integers represented using at most base- digits, padding leading zeros if necessary. For above a fixed base-case threshold, let and write
where and . Define
Expansion gives , so
The algorithm recursively computes only , then uses additions, subtractions and digit shifts to recover the product. For nonnegative inputs, is nonnegative even though it is obtained by subtraction. Signed integers can be handled by multiplying absolute values and restoring the sign separately.
Concept lensAlgebraic
Three evaluations of a quadratic
Let . Then , is the leading coefficient, and . A quadratic is determined by three values, and is the interpolation step. The product is .
Theorem 1.6.2
(Correctness of the three-product identity)
For every radix and every nonnegative inputs split as above, the three recursive products and the recombination formula equal the ordinary integer product .
Theorem 1.6.3
(Padded operation count)
For the implementation below, the number of fixed-radix digit operations is . In particular, its upper bound is asymptotically smaller than the digit-operation bound for direct schoolbook multiplication.
The last statement compares two specified algorithms in a fixed-radix digit-operation model. It is not a lower bound on all possible multiplication algorithms.
Correctness and padding
Proof
(Why the identity is exact and the recursion ends)
Expanding gives . Subtracting and leaves the two cross products. Substituting into the displayed recombination identity reproduces the ordinary expansion of .
Each half has at most digits, but a sum such as can require digits because of a carry. For a simple uniform analysis, pad the arguments of all three recursive calls to digits, even when an argument has fewer significant digits. Use direct multiplication for sizes at most eight. When , the child size is strictly less than , so recursion terminates.
Padding does not change the integers being multiplied. The recombination uses digit shifts by or positions and additions or subtractions of -digit quantities, all implementable in fixed-radix digit operations. By induction on the padded size, the recursive calls return the three exact products, so the identity proves correctness for every input.
Proof X-ray
One product encodes both cross terms
The product of the sums contains all four pairwise products. Removing the already computed low-low and high-high terms leaves exactly the sum of the two cross terms, which is all recombination needs.
Checking digit sizes and carries
Each half is less than , so a sum of two halves is less than . It therefore fits in base- digits, even for radix two. Padding every recursive argument to that length makes the three calls uniform. This is an upper bound on representation length, not an assertion that the leading digit is nonzero.
The intermediate products also have only digits. Each product of two at-most--digit numbers is less than . In the recombination, the cross-term value equals and is nonnegative. Subtracting and from can be implemented with ordinary borrow propagation across a linear number of digits; no negative intermediate is needed if the two known nonnegative products are subtracted in either order.
Multiplying by means shifting the digit representation by positions, or equivalently aligning it at that offset in an output buffer. It is not another recursive multiplication by a general integer. Adding the three aligned contributions takes linear work in their total representation length, with carries handled by the usual digit-addition algorithm.
Comparing the two recurrences
The direct four-product split has a recurrence of the form in an ideal equal-size analysis, leading to quadratic digit work. Karatsuba reduces the branching factor to three, so the number of subproblems grows as while their sizes decrease approximately as . Their combined linear work at level grows roughly like , and the deepest levels dominate at the scale.
The exact rounded recurrence is not literally for every integer . The sum operands may have a carry, and the padded size is . Shifting the size by three gives a clean halving inequality and avoids replacing the actual implementation by a different ideal recurrence. The finite base threshold then handles the smallest cases where that shifted expression alone would not describe a useful split.
Upper bound with rounded sizes
Proof
(Upper bound with rounded sizes)
Let bound the digit work of the padded algorithm. For ,
for a fixed constant , with constant work at sizes at most eight. The added one accounts for a possible carry. Define the shifted size . If a child has size , then
Thus after recursive levels, every node has size at most . There are at most nodes at level . For , every path has reached the base threshold by depth : its size is at most eight. The total nonrecursive work is bounded by a constant times
Both geometric sums are . Indeed, and . The constant-size leaves fit within the same bound. This proves the upper bound, including ceilings and carry padding.
Bounding the geometric sums
For , the depth choice satisfies . Therefore is at most a constant multiple of . Similarly, is at most a constant multiple of
The sums of the level costs are geometric with ratios three and three halves, respectively, so each is within a constant factor of its last term. The logarithmic ceiling changes only that constant. The proof counts both the size-proportional recombination work and the constant contribution per recursion node.
A sequential implementation can reuse temporary storage after each recursive product is returned. Along one active recursion path, padded sizes decrease according to the shifted-halving bound, so the sum of their sizes is . With a constant number of linear-size buffers per active level, this gives auxiliary digit storage apart from the input and output. Running the three recursive calls in parallel or retaining additional copies changes the storage accounting and needs a separate analysis.
Lower bound for this padded implementation
Proof
(Matching lower bound for the padded implementation)
For , the padded algorithm always makes three recursive calls, each of size , even if some leading digits are zero. For sufficiently large, let . Every node above depth has size at least and is therefore nonbase. The recursion tree contains at least nodes at depth .
If each node performs at least one digit operation, this gives a matching lower bound for the specified padded implementation. The padding convention is important: an implementation that skips zero subproducts can do less work on some special inputs. The upper bound remains valid, but this particular per-input lower argument would no longer apply unchanged.
Counterexample mode
The input sums can grow by one digit
In radix ten, two three-digit numbers such as and have a four-digit sum . Treating every sum as a three-digit input without a carry or padding rule makes the recursive-size argument incomplete.
What the exponent compares
Because , taking base-two logarithms gives . Consequently tends to zero as grows. This is the sense in which the stated upper bound improves on the quadratic operation count of the standard fixed-loop schoolbook algorithm. For small inputs, recursion and temporary buffers can have larger constant costs, which is one reason a practical implementation uses a base case.
The standard digit-by-digit method forms individual digit products when both inputs are padded to digits and the loops run over every pair. With fixed radix, each such digit product and carry update has bounded local cost; accumulating the shifted rows gives digit operations. That is an analysis of this particular direct method, not a universal lower bound for integer multiplication.
The choice of eight for the Karatsuba base threshold is also an implementation convention. Any fixed sufficiently large threshold for which above the threshold gives the same asymptotic exponent. Its value changes finite constants and the base cases that must be checked, but not the geometric comparison between three branches and halved sizes. A production implementation may choose the threshold by measurement, while the proof only requires it to be a fixed constant independent of the input length.
The output has at most base- digits because implies . Intermediate buffers may include extra leading zeros from padding, but their lengths remain linear in . This output-size observation supports the stated linear recombination and storage accounting; it does not by itself prove the subquadratic running time.
Worked examples
Worked example 1.6.4
(A decimal multiplication)
Split and at : , , , . The three products are , and . Hence , and recombination gives .
Worked example 1.6.5
(Why the sum product is useful)
For , the cross products are and . Instead of computing them separately, use . The recovered sum is .
Worked example 1.6.6
(An odd digit length)
For , the split uses low digits and at most four high digits. The sum of a low and a padded high part can require six digits, so each recursive call is safely padded to . This is smaller than nine, as required for progress beyond the base threshold.
Worked example 1.6.7
(A zero input)
If and is any nonnegative input, the arithmetic identity returns zero. The specified padded implementation may still make all three recursive calls; its operation count describes that implementation, not an optimization that detects zero and exits early.
Common mistakes
Common mistake
(Using only one cross product)
The middle coefficient is the sum of the two cross products. Replacing it by only one cross product gives the wrong multiplication. The three-product trick works because the product of sums contains both cross terms together.
Common mistake
(Ignoring the carry in the operand sums)
A carry can make the sum operands one digit longer than a half. Ignoring it may produce a recurrence that is not a valid bound for the implementation. The shifted-size inequality handles this extra digit explicitly.
Common mistake
(Reading the exponent as a universal bound)
is an operation count for the padded algorithm under the stated model. It is not a claim that multiplication cannot be done faster by another algorithm, nor that all machine-level operations have the same cost for arbitrary-precision values.
Summary
Karatsuba multiplication replaces four half-size products by three products plus linear recombination. Padding sum operands handles carries, and a shifted-size recursion-tree argument controls ceilings. The resulting fixed-radix digit-operation count is for the specified always-recursing implementation.
Exercises
Quick check
(Expand .)
Multiply out the sum and cancel.
Solution · Answer
Expanding and canceling gives .
Quick check
(For , what recursive argument size is used by the padded implementation?)
Compute and add the carry digit.
Solution · Answer
, so the recursive argument size is six digits.
Quick check
(Why can the sum of two -digit inputs require digits?)
Think of adding the largest possible digits.
Solution · Answer
Their addition can produce a carry out of the highest digit. In radix ten, is an example.
Quick check
(Why does the lower bound in this chapter not apply automatically to an implementation that immediately returns on a zero operand?)
Which object does the lower-bound proof count?
Solution · Answer
The proof counts a full three-branch padded recursion tree. An early-zero check can remove all those calls for some inputs, so the counted tree need not exist in that implementation.