Engineering / Mathematics — Integer Algorithms
Integer Multiplication
Schoolbook multiplication of multiprecision integers, the accumulator requirement, and where the quadratic cost comes from.
Executive summary
Schoolbook multiplication forms every pairwise product of digits and accumulates them into the correct positions, costing a number of digit multiplications equal to the product of the operand lengths.
It remains the method of choice below a crossover point that is surprisingly high in practice, typically in the hundreds or thousands of bits depending on implementation quality.
Learning objectives
- State the schoolbook algorithm and its cost.
- Determine the accumulator width required.
- Recognise when to switch to a subquadratic method.
01The algorithm
Schoolbook multiplication
a with m digits, b with n digitsa · b, at most m + n digits- Allocate a result array of m + n digits, initialised to zero.
- For i from 0 to m−1: set carry c = 0.
- For j from 0 to n−1: compute t = r_{i+j} + aᵢ · bⱼ + c; set r_{i+j} = t mod B, c = t div B.
- Set r_{i+n} = r_{i+n} + c.
- Strip leading zeros and return r.
O(mn) digit operations, so O(ℓ²) for equal lengths02Where the quadratic cost is unavoidable
Every digit of a must interact with every digit of b, because each contributes to the product. Schoolbook does exactly mn digit multiplications, which is the obvious count and for a long time was assumed optimal.
It is not. Karatsuba's method computes the product of two-digit-groups with three multiplications rather than four, by reusing a sum, and recursion drives the exponent down to log₂3 ≈ 1.585. Further methods reduce it further.
- Schoolbook
O(ℓ²)Best below the crossover; simple and cache-friendly - Karatsuba
O(ℓ^1.585)Crossover typically a few hundred bits - Toom–Cook
O(ℓ^1.465) and lowerFamily parameterised by split count - Schönhage–Strassen
O(ℓ log ℓ log log ℓ)FFT-based; crossover in the tens of thousands of bits
03Squaring as a special case
Squaring admits a genuine saving over general multiplication. Since aᵢaⱼ and aⱼaᵢ are equal, the off-diagonal products need computing only once and doubling, roughly halving the digit multiplications.
a² = Σᵢ aᵢ²B^{2i} + 2Σ_{i<j} aᵢaⱼB^{i+j}04Frequently asked questions
Why is the crossover for Karatsuba so high?
Because Karatsuba trades multiplications for additions and recursion overhead, and additions are cheap while function calls and memory traffic are not. A well-optimised schoolbook inner loop with good cache behaviour beats a naive Karatsuba implementation for a long way up.
Does the result always have m + n digits?
At most. It has m + n − 1 or m + n, depending on whether the leading digits produce a carry out. Allocating m + n and stripping is simpler than predicting which.
Is FFT multiplication used in practice?
In general-purpose libraries such as GMP, yes, for very large operands. For cryptographic sizes of a few thousand bits it is not competitive, so RSA implementations rarely reach past Karatsuba or Toom–Cook.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 42-45.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.