Multiprecision Arithmetic

Schoolbook and Karatsuba Multiplication

Quadratic schoolbook multiplication, the Karatsuba three-multiplication identity, and where the crossover between them sits.

Engineering / MathematicsMultiprecision Arithmetic3 min readKV-MATH-0507

Multiplication is the operation whose cost dominates almost every algorithm in this collection. The naive method is quadratic; Karatsuba's identity reduces the exponent, and the crossover between them is a tuning parameter every serious library exposes.

Schoolbook multiplication

The direct method computes every partial product and accumulates. For operands of k and l limbs it performs k times l limb multiplications, each producing a double-width result that must be accumulated with carry.

Cost = O(k * l), or O(k^2) for equal lengthsEach inner step is one multiply-accumulate with carry.

Squaring is cheaper

Squaring admits a genuine saving because off-diagonal partial products appear twice. Computing them once and doubling reduces the limb multiplications by roughly half.

x^2 = sum a_i^2 B^(2i) + 2 * sum over i<j of a_i a_j B^(i+j)The cross terms are computed once and doubled.

The Karatsuba identity

Split each operand into high and low halves. The naive product needs four half-size multiplications; Karatsuba needs three.

x = x1 B^m + x0, y = y1 B^m + y0

xy = x1 y1 B^(2m) + ((x1+x0)(y1+y0) - x1 y1 - x0 y0) B^m + x0 y0Three half-size products instead of four, at the cost of extra additions.

Karatsuba multiplication

SplitDivide both operands at limb m, roughly half the length.
Three productsCompute the high product, the low product, and the product of the two sums.
CombineSubtract the high and low products from the middle one, then assemble with shifts and additions.
RecurseApply the same method to each half-size product until the crossover threshold is reached.

Complexity and crossover

T(k) = 3 T(k/2) + O(k) => T(k) = O(k^log2(3)) = O(k^1.585)The saving comes entirely from three recursive calls instead of four.

Method selection by size — thresholds are machine-specific
Operand size	Preferred method	Reason
Below ~20-40 limbs	Schoolbook	Karatsuba's additions and recursion overhead dominate
Middle range	Karatsuba	Exponent advantage takes over
Very large	Toom-Cook or FFT-based	Further exponent reductions, larger overheads still

Frequently Asked Questions

Why does Karatsuba use three multiplications rather than four?

The middle coefficient of the product can be recovered from the product of the sums minus the two outer products, which were needed anyway. The fourth multiplication is redundant once you have the other three.

Is Karatsuba worth implementing if a library is available?

No. But understanding it matters, because the same split-and-recombine idea reappears in polynomial multiplication — see polynomial multiplication.

Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.2.3. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.

Schoolbook and Karatsuba Multiplication

Schoolbook multiplication

Squaring is cheaper

The Karatsuba identity

Complexity and crossover

Frequently Asked Questions

Continue learning