Multiprecision Arithmetic
Multiprecision Integer Representation
How arbitrary-precision integers are stored, why the base is chosen to match the machine word, and the consequences for every algorithm above.
Engineering / MathematicsMultiprecision Arithmetic2 min readKV-MATH-0505
Every algorithm in this collection operates on integers far larger than a machine word. The representation chosen for those integers sets the cost of every operation performed on them, so it is worth understanding before anything else.
Positional representation in base B
A multiprecision integer is stored as a sign together with an array of digits in some base B, least significant first. The digits are conventionally called limbs or words.
Choosing the base
The base is chosen to be a power of two matching the machine word — typically B = 2^32 or B = 2^64. Two reasons dominate.
Hardware alignment
Addition, multiplication and division of single limbs map directly onto machine instructions. A non-power-of-two base would require explicit reduction after every operation.
Carry handling
With a power-of-two base, extracting the carry from a sum is a shift and a mask rather than a division.
Normalisation
Two invariants are maintained by every well-behaved implementation, and violating either produces bugs that surface far from their cause.
- The most significant limb is non-zero, so the length is unique.
- Zero has a canonical representation, usually length zero, and its sign is not consulted.
Cost consequences
| Operation | Cost in limbs | Notes |
|---|---|---|
| Addition, subtraction | O(k) | Linear, carry propagation only |
| Comparison | O(k) worst case | Length check first, usually O(1) |
| Multiplication | O(k^2) schoolbook | See Karatsuba |
| Division | O(k^2) | Larger constant than multiplication |
| Shift by whole limbs | O(k) or free | Often just an offset |
Frequently Asked Questions
Should I write my own multiprecision library?
Why store limbs least significant first?
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.2.1. 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.