The layer everything else assumes is free
Multiprecision integers are stored as arrays of fixed-size digits called limbs, in a base matched to the machine word. Addition is linear in the operand length; multiplication is not, and the crossover points between schoolbook, Karatsuba, Toom–Cook and FFT-based multiplication determine the practical cost of every higher-level algorithm. Division and modular reduction are the awkward operations, and are usually restructured to avoid them.
Learning objectives
- Describe the limb representation of a multiprecision integer and its sign handling.
- State the asymptotic costs of the principal multiplication algorithms.
- Explain why crossover points must be measured rather than assumed.
- Choose between Montgomery, Barrett and plain reduction for a modular workload.
- Identify the base ring appropriate to a given computation.
Section 01Representation
A non-negative multiprecision integer is an array of limbs (a0, …, an−1) in base B, together with a length and a sign. The value is
The base B is chosen as 232 or 264 so that a limb fits a machine register and carries can be detected cheaply. Two conventions compete for negative numbers: sign-magnitude, which keeps a separate sign flag, and two's-complement extension. Sign-magnitude dominates in number-theoretic libraries because the algorithms overwhelmingly operate on magnitudes and branch on sign at a higher level.
Every routine must return a normalised result: no leading zero limbs, and zero represented canonically with length 0 and positive sign. Non-normalised values are the classic source of comparison bugs, because two representations of the same integer then compare unequal.
Section 02Addition, subtraction and comparison
Addition and subtraction are linear. The only subtlety is carry and borrow propagation, which in the worst case ripples the full length of the operand but on random inputs terminates almost immediately.
- Set carry ← 0 and i ← 0.
- While i < max(m, n): set t ← ai + bi + carry (absent limbs read as 0).
- Set ci ← t mod B and carry ← ⌊t / B⌋. On a machine this is a single add-with-carry.
- Increment i and repeat.
- If carry ≠ 0, append it as the leading limb.
- Normalise and return.
Comparison is by length first, then by limbs from the most significant downward. Because the values are normalised, the length comparison is exact and usually decides immediately.
Section 03Multiplication and its crossovers
Multiplication is where algorithm choice matters. Four families are used in practice, and a serious library implements all of them with measured thresholds.
| Method | Cost | Idea | Typical regime |
|---|---|---|---|
| Schoolbook | O(n2) | Direct convolution of limb arrays | Up to roughly 20–40 limbs |
| Karatsuba | O(n1.585) | Split in two; three half-size products instead of four | Tens to a few hundred limbs |
| Toom–Cook (3-way and up) | O(n1.465) for 3-way | Split in k parts; evaluate, multiply pointwise, interpolate | Hundreds to thousands of limbs |
| Schönhage–Strassen / FFT | O(n log n log log n) | Multiplication as cyclic convolution via number-theoretic transform | Many thousands of limbs and above |
Published crossover points are not portable. Cache size, register width, multiplier latency and compiler behaviour all move them. A library that hard-codes another machine's thresholds can be several times slower than one that tunes them at build time. Treat crossovers as measured constants, never as inherited ones.
Section 04Division and modular reduction
Division is the expensive primitive. The classical algorithm processes one quotient limb at a time, estimating each from the leading limbs of the running remainder and correcting a bounded number of times. Correctness of the estimate depends on normalisation: the divisor is first scaled so that its leading limb has its top bit set, which bounds the estimation error to at most two.
Because division is costly, modular arithmetic avoids it wherever a modulus is reused.
Plain reduction
Divide and take the remainder. Correct, simple, and the right choice when the modulus changes on every operation.
Barrett reduction
Precompute a scaled reciprocal of the modulus; replace division by two multiplications and a correction. Suits a fixed modulus with mixed operations.
Montgomery reduction
Work in a transformed residue domain where reduction is exact shifting. Dominant for long chains of modular multiplications, such as modular exponentiation.
Montgomery form costs a conversion in and out. It wins when many multiplications happen between conversions — exponentiation is the canonical case — and loses when a single reduction is needed. It also requires an odd modulus.
Section 05Choosing the base ring
A computation should be carried out in the smallest ring in which it is valid. Working in a larger ring than necessary is the most common source of avoidable cost.
| Ring | Exact? | Cost driver | Typical use |
|---|---|---|---|
| ℤ (integers) | Yes | Operand growth | Resultants, HNF, exact linear algebra |
| ℚ (rationals) | Yes | GCD of numerator and denominator at every step | Avoid where possible — clear denominators and work in ℤ |
| ℤ/nℤ | Yes | Modular reduction | Modular algorithms, CRT reconstruction |
| Fq (finite field) | Yes | Field arithmetic | Polynomial factorisation, curve point counting |
| ℝ, ℂ (floating point) | No | Precision management and error tracking | Regulators, root finding, LLL with floating Gram–Schmidt |
Naive computation over ℚ invokes a GCD at every arithmetic step and the intermediate expressions grow explosively. Standard practice is to clear denominators once, work entirely in ℤ, and divide out a single content factor at the end.
ReferenceFrequently asked questions
Why base 2<sup>64</sup> rather than a decimal base?
Because carry detection, multiplication and shifting then map to single machine instructions. Decimal bases are used only where decimal output is the dominant operation, which is rare in number-theoretic work.
Is FFT multiplication worth implementing?
Only if the workload genuinely reaches operands of many thousands of limbs. Below that, its large constant factor and precision management make it slower than Toom–Cook. Most applications should link a tuned library rather than implement this layer at all.
Does floating point have any legitimate place here?
Yes, but always with an error bound and an exact fallback. Floating-point Gram–Schmidt inside LLL is standard practice and is safe precisely because the reduction conditions are re-verified in exact arithmetic when the floating computation looks marginal.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
Knuth, The Art of Computer Programming, volume 2, remains the reference treatment of multiprecision arithmetic. Current implementations of record are GMP and the arithmetic cores of PARI/GP and FLINT.
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.