Python Unlimited Precision Integers at the C Level

Python avoids integer overflow by ditching fixed-width CPU registers in favor of dynamic, heap-allocated data structures managed by the CPython runtime. Rather than relying on native C types such as int64_t or long long, CPython implements integers via a custom type called PyLongObject. This article explores how CPython defines this structure under the hood, how it packs arbitrarily large numeric values into arrays of "digits," and how the underlying C implementation manages signs and dynamic memory.

The PyLongObject Structure

In CPython, every integer is an instance of PyLongObject. At the C level, this object is a variable-length object that extends PyVarObject:

struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};

The macro PyObject_VAR_HEAD expands to include standard object metadata:

• A reference count (ob_refcnt) for garbage collection.
• A pointer to the type object (ob_type), which resolves to &PyLong_Type.
• An item count/size field (ob_size), typed as Py_ssize_t.

Directly following this header is the flexible array member ob_digit, which holds the actual numeric payload.

Sign and Length Management via ob_size

CPython optimizes memory by using the ob_size field for two distinct purposes: the length of the integer and its sign.

• Absolute Size: The absolute value abs(ob_size) specifies the number of elements allocated and used in the ob_digit array.
• Sign: If ob_size > 0, the integer is positive. If ob_size < 0, the integer is negative. If ob_size == 0, the value is zero, and ob_digit contains no elements.

By encoding the sign into ob_size, individual digits inside ob_digit can remain strictly unsigned, which significantly simplifies bitwise operations and arithmetic logic in C.

Chunking via Radix Representation (ob_digit)

Computers cannot natively execute arithmetic on numbers with hundreds or thousands of bits in a single CPU instruction. To handle this, Python breaks the number down into smaller chunks, effectively implementing a positional numeral system with a very large base.

The type digit is an alias for uint32_t on 64-bit platforms (or uint16_t on 32-bit platforms). Instead of utilizing all 32 bits of each element:

• On 64-bit systems, Python uses a 30-bit base: \(2^{30} = 1,073,741,824\).
• On 32-bit systems, Python uses a 15-bit base: \(2^{15} = 32,768\).

The digits are stored in little-endian order within the ob_digit array: ob_digit[0] holds the least significant 30 bits, ob_digit[1] holds the next 30 bits, and so on.

The integer value \(V\) is represented as:

\[V = \text{sgn}(\text{ob\_size}) \times \sum_{i=0}^{|\text{ob\_size}| - 1} \text{ob\_digit}[i] \times 2^{30 \times i}\]

Why 30-Bit Digits on 64-Bit Systems?

Reserving the top 2 bits (or 34 bits in a 64-bit register) prevents arithmetic overflow during primitive operations. When multiplying two 30-bit integers, the maximum product requires 60 bits:

\[ (2^{30} - 1) \times (2^{30} - 1) < 2^{60} \]

Because \(2^{60} < 2^{64}\), intermediate multiplication and addition steps fit into standard C unsigned 64-bit integers (uint64_t, often aliased as twodigits) without carrying out manual overflow checks at every assembly-level instruction.

Memory Allocation and Immutability

Because Python integers are immutable, the ob_digit array is allocated to an exact fit when the integer is created.

1. Small Integers: To avoid heap allocation churn for ubiquitous numbers, CPython pre-allocates an array of small integer objects in the range \([-5, 256]\) at startup. Any reference to these numbers reuses the existing singleton pointers.
2. Dynamic Integers: For numbers outside this range, Python calculates the required number of digit units via _PyLong_New(size) and allocates contiguous memory matching sizeof(PyVarObject) + (size * sizeof(digit)).

Arithmetic Algorithms

When operations cause an integer to exceed its current capacity, CPython allocates a new PyLongObject with an expanded ob_digit array:

• Addition/Subtraction: Uses standard column-wise addition/subtraction with carry propagation across digits, running in \(\mathcal{O}(N)\) time where \(N\) is the number of digits.
• Multiplication: For smaller numbers, CPython uses the classic grade-school \(\mathcal{O}(N^2)\) algorithm. When inputs exceed a threshold (traditionally around 70 digits), CPython automatically switches to the Karatsuba multiplication algorithm, reducing time complexity to approximately \(\mathcal{O}(N^{1.58})\).

By abstracting dynamic array management and carrying operations behind the C-level PyLongObject, Python exposes an integer type that scales seamlessly with available system memory without user intervention.