Engineering / Mathematics — Integer Algorithms
Representing Large Integers
Positional representation of multiprecision integers, base selection, sign handling and normalisation invariants.
Executive summary
A multiprecision integer is an array of digits in a base chosen to match the machine word, together with a sign and a length. Every arithmetic routine depends on invariants of this representation being maintained.
The choices — base, digit order, sign convention, normalisation — are implementation decisions with measurable consequences and no single correct answer.
Learning objectives
- Describe positional representation and prove uniqueness.
- Select a base appropriate to a machine architecture.
- State the invariants an implementation must maintain.
01Positional representation
Base representation
For any base B ≥ 2, every non-negative integer a has a unique representation
a = Σ aᵢ B^i with 0 ≤ aᵢ < B and leading digit non-zero.
Existence and uniqueness both follow from repeated division with remainder. The number of digits is ⌊log_B a⌋ + 1, so the length in bits is roughly log₂ a regardless of base — the base affects constants and implementation, not asymptotic size.
len_B(a) = ⌊log_B a⌋ + 1 for a ≥ 1, len_B(0) = 1 by convention02Choosing the base
The base is chosen so that a digit fits a machine word and the product of two digits fits the widest available accumulator.
| Architecture | Typical base | Product fits |
|---|---|---|
| 32-bit, 64-bit accumulator | 2³² | 64-bit product register |
| 64-bit, 128-bit accumulator | 2⁶⁴ | 128-bit product via compiler intrinsic |
| Portable C, no wide type | 2³² with 32-bit digits | Split multiplication into halves |
| Decimal output required | 10⁹ | Simplifies printing at arithmetic cost |
03Invariants and sign
Sign-magnitude representation — an unsigned digit array plus a separate sign flag — is standard, in contrast to the two's complement used for fixed-width machine integers. It simplifies multiplication and division at the cost of a branch in addition.
- No leading zeros. The most significant digit is non-zero, except for the value zero itself. Without this, equality comparison and length queries become unreliable.
- Canonical zero. Zero has length one and a positive sign flag, so that no negative zero exists.
- Digits in range. Every digit satisfies
0 ≤ aᵢ < Bafter every operation; carries must be fully propagated before a routine returns. - Length matches capacity. The stored length reflects the significant digits, not the allocated buffer.
04Frequently asked questions
Little-endian or big-endian digit order?
Little-endian — least significant digit first — is nearly universal in libraries, because it makes growing a number an append rather than a shift, and index i corresponds to the coefficient of B^i without an offset computation.
Why not use two's complement for multiprecision?
Because it requires a fixed width to define the sign bit position, and multiprecision numbers have no fixed width. Sign-magnitude keeps the magnitude a plain unsigned array whose length can change freely.
Does the base choice affect asymptotic complexity?
No. Changing base multiplies the digit count by a constant factor, which asymptotic notation absorbs. It affects the constant, which for a heavily used library is worth optimising carefully.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 39-41.
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.