Multiprecision Arithmetic
Asymptotic Cost of Integer Multiplication
The M(n) abstraction, the hierarchy of multiplication algorithms, and why downstream bounds are quoted in terms of M(n) rather than fixed exponents.
Engineering / MathematicsMultiprecision Arithmetic2 min readKV-MATH-0508
Cost statements throughout this collection are written in terms of M(n), the cost of multiplying two n-bit integers. Keeping the multiplication cost symbolic rather than fixed makes every downstream bound automatically inherit improvements.
The hierarchy
| Method | Complexity | Practical range |
|---|---|---|
| Schoolbook | O(n^2) | Small operands |
| Karatsuba | O(n^1.585) | Tens to hundreds of limbs |
| Toom-Cook (3-way) | O(n^1.465) | Hundreds of limbs |
| FFT-based | Near-linear up to log factors | Very large operands |
Why write M(n)
Many operations reduce to a bounded number of multiplications. Quoting their cost in terms of M(n) keeps the statement true regardless of which multiplication method is in use.
- Division with remainder
- O(M(n)) by Newton iteration on the reciprocal
- Extended GCD
- O(M(n) log n) by the half-GCD method
- Modular exponentiation
- O(M(n) * e) where e is the exponent bit length — see binary powering
- Integer square root
- O(M(n)) by Newton iteration
Where the abstraction leaks
Two situations require care.
Memory, not time, binds
Sieving methods are limited by memory bandwidth and capacity rather than arithmetic throughput. M(n) says nothing useful about them.
Many small operations
When the operands fit in one or two limbs, the constant overhead of a general multiplication routine dominates its asymptotic cost. Finite field arithmetic frequently lives here.
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.