How Arbitrary-Precision Math Represents Large Integers

Arbitrary-precision arithmetic libraries—often called “bignum” or “BigInt” libraries—allow computers to perform calculations on integers of virtually unlimited size, constrained only by available system memory. While standard CPU architectures restrict native integer operations to fixed register sizes (typically 32 or 64 bits), arbitrary-precision libraries bypass this hardware limitation by decomposing a massive integer into an ordered sequence of machine-sized binary words, often referred to as “limbs” or “digits.” This article explains the data structures, base conversions, and memory strategies these libraries use to represent unbounded integers.

The Concept of Limbs and Generalized Radix

To store a number larger than the CPU’s register capacity, arbitrary-precision libraries view the large integer as a polynomial evaluated at a very large base \(B\). In this system, the base is chosen as a power of two, typically matching the native word size of the CPU:

\[B = 2^W\]

where \(W\) is the word length (usually 32 or 64 bits).

Any arbitrary integer \(N\) is represented as:

\[N = \sum_{i=0}^{n-1} a_i \cdot B^i = a_0 + a_1 B + a_2 B^2 + \dots + a_{n-1} B^{n-1}\]

Each coefficient \(a_i\) is a single machine word (a “limb”) bounded by \(0 \le a_i < B\). Instead of using base 10 (decimal) or base 2 (single bits), the computer operates in base \(2^{32}\) or base \(2^{64}\). This maximizes computational efficiency by allowing standard CPU arithmetic instructions to process entire limbs in a single clock cycle.

Internal Memory Representation

At the implementation level (such as in libraries like GMP, OpenSSL’s BIGNUM, or language runtimes like Python and Rust), a large integer is stored as a structured data type containing three primary components:

  1. Limb Array (Pointer/Buffer): A contiguous array of unsigned native integers (e.g., uint32_t or uint64_t) containing the coefficients \(a_0, a_1, \dots, a_{n-1}\).
  2. Length/Size Field: An integer indicating how many limbs are currently in use to represent the number.
  3. Capacity Field: An integer indicating the total allocated memory capacity for the limb array, enabling dynamic resizing without constant reallocations.

Endianness of Limbs

Most arbitrary-precision libraries store limbs in little-endian limb order, meaning the least significant limb (\(a_0\)) is located at index 0 of the array, and the most significant limb (\(a_{n-1}\)) is located at the highest index.

This layout simplifies arithmetic operations: * Addition and subtraction naturally start at index 0 and propagate carries upward through increasing indices. * Scaling the number up (adding higher-order limbs) only requires appending elements to the end of the array rather than shifting existing memory.

Sign Handling: Sign-Magnitude vs. Two’s Complement

Standard fixed-width CPU integers use two’s complement representation for negative numbers. However, arbitrary-precision libraries predominantly use sign-magnitude representation for large integers.

In a sign-magnitude scheme: * The magnitude (absolute value) is stored purely as an array of unsigned binary words. * The sign is stored separately as a single boolean flag, an enum, or the sign of the length field (e.g., a negative length denotes a negative number).

Sign-magnitude is preferred because: * It eliminates the need for sign-extension across an arbitrary number of limbs. * Multiplication and division algorithms are significantly simpler when operating purely on unsigned magnitudes, with the sign computed independently using an XOR operation on the operands’ signs.

Word Utilization: Full-Width vs. Unpacked Words

Libraries choose between two main strategies for sizing limbs:

Through this combination of large-radix polynomials, contiguous memory buffers, and sign-magnitude encoding, arbitrary-precision libraries achieve high performance while supporting numbers of theoretically infinite magnitude.