vault

CPython Integer Internals

16 min read

CPython Integer Internals

In CPython 3.14 the built-in int is an arbitrary-precision integer: a heap object (PyLongObject) that stores a value as a little-endian array of 30-bit digits, so it can grow to any size your memory allows rather than overflowing at 64 bits like a machine integer. The number’s magnitude lives in the ob_digit[] array, while a single packed word called lv_tag holds both the sign and the digit count (longintrepr.h). Since CPython 3.12 (the layout that landed in pycore_long.h), values small enough to fit in one digit are flagged “compact” and read with a branch-free fast path. Arithmetic uses school-book algorithms for small operands and switches to Karatsuba multiplication once both operands exceed 70 digits. This note explains that representation and arithmetic; the pre-allocated cache of the smallest integers is a separate concern owned by Small Integer and String Caching.

Mental Model

Think of a Python int not as a 64-bit register but as a string of digits in base 2³⁰, wrapped in the universal object header described in PyObject and the Object Header. A machine int is a fixed slab of bits that silently wraps around on overflow; a Python int is a variable-length record that grows — every time the magnitude crosses a 2³⁰ boundary, CPython allocates one more 32-bit slot in ob_digit[]. The “digits” are not decimal digits and not single bits: each is a number in the range 0 .. 2³⁰−1, and the whole value is reconstructed by treating them as place values of base 2³⁰.

The crucial design tension is that most integers in a running program are tiny — loop counters, list indices, small arithmetic results — yet the representation must also handle a 10⁰⁰⁰-digit factorial without changing type. CPython resolves this by special-casing the common case: a “compact” integer (at most one digit, i.e. magnitude < 2³⁰) packs its sign and size into the lv_tag word so that reading its value is a single multiply with no loop, while genuinely large integers fall back to the general digit-array machinery.

flowchart TD
    A["Python int object<br/>(PyLongObject)"] --> B["PyObject_HEAD<br/>ob_refcnt, ob_type"]
    A --> C["long_value: _PyLongValue"]
    C --> D["lv_tag (uintptr_t)<br/>bits 0-1: sign (0=+, 1=zero, 2=-)<br/>bit 2: 1 if small-int singleton<br/>bits 3+: digit count (ndigits)"]
    C --> E["ob_digit[]: array of 30-bit digits<br/>little-endian, base 2^30<br/>value = sign * SUM(digit[i] * 2^(30*i))"]
    D -->|"ndigits <= 1<br/>(magnitude < 2^30)"| F["COMPACT: value read<br/>branch-free from one digit"]
    D -->|"ndigits >= 2"| G["FULL bignum:<br/>school-book / Karatsuba arithmetic"]

Diagram: the anatomy of a PyLongObject. The insight to extract is that the single lv_tag word does double duty — it encodes both sign and length, and one of its bits (bit 2) marks the pre-cached small-int singletons — so the hot path for tiny integers never touches the digit array beyond ob_digit[0].

Mechanical Walk-through

The object layout

The C declaration of the integer object is short (longintrepr.h):

typedef struct _PyLongValue {
    uintptr_t lv_tag; /* Number of digits, sign and flags */
    digit ob_digit[1];
} _PyLongValue;
 
struct _longobject {
    PyObject_HEAD
    _PyLongValue long_value;
};

Line by line:

  • PyObject_HEAD — the universal header (ob_refcnt reference count and ob_type type pointer) that every object carries; see PyObject and the Object Header. On a 64-bit CPython build this is 16 bytes.
  • uintptr_t lv_tag — a single pointer-sized word (8 bytes on 64-bit) holding the sign and the digit count, packed together (described below). uintptr_t is an unsigned integer guaranteed wide enough to hold a pointer, so on 64-bit it is 64 bits.
  • digit ob_digit[1] — the digit array, declared with length 1 but actually allocated with as many slots as the value needs. This is the classic C “flexible array member” idiom: the allocator over-allocates so ob_digit[0] .. ob_digit[ndigits-1] are all valid. The header comment guarantees “We always allocate memory for at least one digit, so accessing ob_digit[0] is always safe.”

A digit is a 30-bit value held in a 32-bit container. The configurable parameters (longintrepr.h):

#if PYLONG_BITS_IN_DIGIT == 30
typedef uint32_t digit;
typedef int32_t sdigit; /* signed variant of digit */
typedef uint64_t twodigits;
typedef int64_t stwodigits; /* signed variant of twodigits */
#define PyLong_SHIFT    30
...
#define PyLong_BASE     ((digit)1 << PyLong_SHIFT)
#define PyLong_MASK     ((digit)(PyLong_BASE - 1))

Walking the symbols:

  • digit is uint32_t: each digit is stored in 32 bits but only the low 30 are used. sdigit is its signed twin (int32_t).
  • twodigits is uint64_t — a type wide enough to hold the product of two digits without overflow (two 30-bit numbers multiply to at most 60 bits). stwodigits is the signed twin. This is the workhorse type for carries in arithmetic.
  • PyLong_SHIFT is 30 — the number of bits per digit, i.e. the base is 2³⁰.
  • PyLong_BASE is 1 << 30 = 1073741824, the radix. PyLong_MASK is PyLong_BASE − 1 = 0x3FFFFFFF, used to strip a value down to one digit with x & PyLong_MASK.

Why 30 bits and not 32?

Using only 30 of the 32 bits leaves headroom: the multiply-and-carry inner loops can accumulate several digit-products in a 64-bit twodigits accumulator before normalizing, without the carry ever overflowing 64 bits. A full 32-bit digit would force more frequent (and more awkward) carry propagation. The header also documents a 15-bit alternative (PYLONG_BITS_IN_DIGIT == 15) for platforms lacking a fast 64-bit integer type; standard 64-bit builds use 30. (longintrepr.h)

How the value is reconstructed

The absolute value of an integer is, per the header comment, SUM(for i=0 through ndigits-1) ob_digit[i] * 2**(PyLong_SHIFT*i) — a positional number in base 2³⁰, least-significant digit first. In a normalized number the top digit ob_digit[ndigits-1] is never zero (so there are no leading-zero digits), and every digit satisfies 0 <= ob_digit[i] <= PyLong_MASK. The sign is applied separately, from lv_tag.

The lv_tag: sign and size in one word

This is the 3.12-era redesign. Before it, CPython used ob_size (a signed Py_ssize_t in the variable-object header) where the sign of the size encoded the sign of the number and its magnitude was the digit count. That conflated the object header with integer semantics. The current layout puts everything in lv_tag (pycore_long.h):

/* Long value tag bits:
 * 0-1: Sign bits value = (1-sign), ie. negative=2, positive=0, zero=1.
 * 2: Set to 1 for the small ints
 * 3+ Unsigned digit count
 */
#define SIGN_MASK 3
#define SIGN_ZERO 1
#define SIGN_NEGATIVE 2
#define NON_SIZE_BITS 3
#define IMMORTALITY_BIT_MASK (1 << 2)

Reading the bit assignments:

  • Bits 0–1 hold the sign, encoded as (1 − sign): a positive number stores 0, zero stores 1, and a negative number stores 2. SIGN_MASK (= 3 = binary 11) isolates these two bits.
  • Bit 2 (IMMORTALITY_BIT_MASK, value 4) is set to 1 for the pre-allocated small-int singletons; those objects are also immortal (their reference count is never touched). The cache itself is a sibling topic.
  • Bits 3 and up (NON_SIZE_BITS = 3, meaning the size starts at bit 3) hold the unsigned digit count, ndigits.

So lv_tag >> 3 gives the digit count and lv_tag & 3 gives the sign code. Reading those out (pycore_long.h):

static inline Py_ssize_t
_PyLong_DigitCount(const PyLongObject *op)
{
    assert(PyLong_Check(op));
    return (Py_ssize_t)(op->long_value.lv_tag >> NON_SIZE_BITS);
}
 
static inline bool
_PyLong_IsZero(const PyLongObject *op)
{ return (op->long_value.lv_tag & SIGN_MASK) == SIGN_ZERO; }
 
static inline bool
_PyLong_IsNegative(const PyLongObject *op)
{ return (op->long_value.lv_tag & SIGN_MASK) == SIGN_NEGATIVE; }
 
static inline bool
_PyLong_IsPositive(const PyLongObject *op)
{ return (op->long_value.lv_tag & SIGN_MASK) == 0; }
  • _PyLong_DigitCount right-shifts away the 3 low bits, leaving ndigits.
  • The three sign predicates each mask off the low two bits and compare against the documented code. Note _PyLong_IsZero checks for SIGN_ZERO == 1, the deliberate special encoding that lets zero be distinguished from a positive number with zero digits.

Constructing a tag is the inverse:

#define TAG_FROM_SIGN_AND_SIZE(sign, size) \
    ((uintptr_t)(1 - (sign)) | ((uintptr_t)(size) << NON_SIZE_BITS))

Given a numeric sign (-1, 0, or 1) and a digit count size, it stores (1 − sign) in the low bits and shifts size up by 3. So True is literally TAG_FROM_SIGN_AND_SIZE(1, 1) and False is TAG_FROM_SIGN_AND_SIZE(0, 0) — because bool is an int subclass.

Compact integers — the fast path

A “compact” integer is one whose magnitude fits in a single digit (< 2³⁰), so its value can be computed without iterating the digit array. The test and the value extraction are defined inline so the compiler can fold them into arithmetic (pycore_long.h and longintrepr.h):

static inline int
_PyLong_IsCompact(const PyLongObject* op) {
    assert(PyType_HasFeature(op->ob_base.ob_type, Py_TPFLAGS_LONG_SUBCLASS));
    return op->long_value.lv_tag < (2 << _PyLong_NON_SIZE_BITS);
}
 
static inline Py_ssize_t
_PyLong_CompactValue(const PyLongObject *op)
{
    Py_ssize_t sign;
    assert(PyType_HasFeature(op->ob_base.ob_type, Py_TPFLAGS_LONG_SUBCLASS));
    assert(PyUnstable_Long_IsCompact(op));
    sign = 1 - (op->long_value.lv_tag & _PyLong_SIGN_MASK);
    return sign * (Py_ssize_t)op->long_value.ob_digit[0];
}
  • _PyLong_IsCompact returns true when lv_tag < (2 << 3) = 16, i.e. when the digit count (lv_tag >> 3) is 0 or 1. (Ignoring bit 2 here is safe because the comparison is against the size field.)
  • _PyLong_CompactValue reconstructs the signed value: sign becomes 1 − (lv_tag & 3), which maps positive→+1, zero→0, negative→−1; multiplying by the single digit ob_digit[0] gives the value directly, no loop. The result fits in a Py_ssize_t “with at least one bit to spare,” per the source comment — exactly the headroom the arithmetic fast paths rely on.

In longobject.c this surfaces as a macro #define medium_value(x) ((stwodigits)_PyLong_CompactValue(x)), and a fast test is_medium_int that lets addition, subtraction, and multiplication of two compact ints execute as a single native operation before re-boxing the result.

Arithmetic: school-book and Karatsuba

The multiplication fast path

long_mul first checks whether both operands are compact (longobject.c):

long_mul(PyLongObject *a, PyLongObject *b)
{
    /* fast path for single-digit multiplication */
    if (_PyLong_BothAreCompact(a, b)) {
        stwodigits v = medium_value(a) * medium_value(b);
        return _PyLong_FromSTwoDigits(v);
    }
    PyLongObject *z = k_mul(a, b);
    ...

If both fit in one digit, the product of two values < 2³⁰ fits in a signed 64-bit stwodigits, so the whole multiplication is one native multiply and a re-box — no allocation of a digit array, no carries. Only when an operand is genuinely large does it call k_mul.

School-book multiplication (x_mul)

For modest operands, CPython uses the quadratic grade-school algorithm — multiply every digit of a by every digit of b, accumulating into a result array of size_a + size_b digits with carry propagation. The source comment is explicit (longobject.c):

/* Grade school multiplication, ignoring the signs.
 * Returns the absolute value of the product, or NULL if error.
 */
static PyLongObject *
x_mul(PyLongObject *a, PyLongObject *b)

When a == b (squaring) it takes a special path “per HAC, Algorithm 14.16,” exploiting that each off-diagonal partial product in the multiplication pyramid appears twice, giving “slightly less than a 2x speedup.” The general loop runs in O(size_a × size_b) digit multiplications.

Karatsuba multiplication (k_mul)

Once both operands are large the quadratic cost dominates, so CPython switches to Karatsuba, an O(n^{log₂3}) ≈ O(n^{1.585}) divide-and-conquer scheme (Knuth Vol. 2, §4.3.3). The decomposition, quoted from the source (longobject.c):

/* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
 * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh  + ah*bh + al*bl
 * Then the original product is
 *     ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
 * By picking X to be a power of 2, "*X" is just shifting, and it's
 * been reduced to 3 multiplies on numbers half the size.
 */

Walking the algebra: split each operand at a digit boundary into a high half (ah, bh) and a low half (al, bl), where X is 2^(30·shift). The naive expansion needs four half-size products (ah·bh, ah·bl, al·bh, al·bl). Karatsuba computes only three — ah·bh, al·bl, and the single product k = (ah+al)·(bh+bl) — and recovers the cross term as k − ah·bh − al·bl. Trading a multiply for a few additions is the whole win, because additions are linear and multiplies are the expensive part. Multiplying X is just a digit shift since X is a power of two.

The crossover is governed by a compile-time cutoff:

/* For int multiplication, use the O(N**2) school algorithm unless
 * both operands contain more than KARATSUBA_CUTOFF digits ...
 */
#define KARATSUBA_CUTOFF 70
#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)

k_mul arranges b to be the larger operand, then falls back to school-book multiplication when the smaller operand is below the cutoff (longobject.c):

    /* Use gradeschool math when either number is too small. */
    i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
    if (asize <= i) {
        if (asize == 0)
            return (PyLongObject *)PyLong_FromLong(0);
        else
            return x_mul(a, b);
    }
  • KARATSUBA_CUTOFF is 70 digits (base 2³⁰), i.e. roughly 70 × 30 ≈ 2100 bits, or ~630 decimal digits. Below this, the recursion overhead of Karatsuba is not worth it and grade school wins.
  • Squaring uses double the cutoff (KARATSUBA_SQUARE_CUTOFF = 140) because x_mul’s squaring path is already fast.
  • There is a further refinement, “Lopsided multiplication,” when b has at least twice the digits of a: it slices b and calls k_mul on balanced pieces to avoid a degenerate split.

Division uses school-book long division (x_divrem), and CPython 3.14 can offload some very large-integer operations to a pure-Python helper module (_pylong, gated by WITH_PYLONG_MODULE) that implements asymptotically faster algorithms for base conversion. (longobject.c)

Memory growth — sys.getsizeof

Because the object grows one 32-bit slot at a time, sys.getsizeof reveals the layout directly. Measured on CPython 3.14.5 (Fedora, 64-bit), confirming the source layout:

>>> import sys
>>> sys.getsizeof(0)            # 28  (zero stores no digits but the slot is allocated)
28
>>> sys.getsizeof(1)            # 28  (one 30-bit digit, magnitude < 2**30)
28
>>> sys.getsizeof(2**30 - 1)   # 28  (still one digit: largest 1-digit value)
28
>>> sys.getsizeof(2**30)       # 32  (crosses 2**30 -> a second digit appears)
32
>>> sys.getsizeof(2**60)       # 36  (three digits)
36
>>> sys.getsizeof(2**100)      # 40  (four digits)
40
>>> sys.getsizeof(10**100)     # 72  (a 333-bit number, 12 digits)
72

Reading the numbers: the base object is 28 bytes on this build — 16 bytes of PyObject_HEAD, 8 bytes of lv_tag, and at least 4 bytes for ob_digit[0] (the always-allocated first digit; the trailing 4 bytes you might expect from alignment are absorbed because the digit slot rounds the struct out). Each additional 30-bit digit adds 4 bytes. The jump from 2**30 − 1 (28 bytes) to 2**30 (32 bytes) is the visible moment a second digit is allocated. This is the most concrete way to see arbitrary precision: a numpy.int64 is always 8 bytes and overflows; a Python int is 28+ bytes and never overflows, paying memory and indirection for that guarantee.

Build dependence

The exact base size depends on pointer width and build options. The 28-byte base above is a CPython 3.14.5 CPython build on 64-bit Linux. A 32-bit build, a free-threaded (Py_GIL_DISABLED) build, or a debug build will report different numbers. Quote sys.getsizeof from the interpreter you actually run, not from this note.

How this differs from a fixed-width machine int

A C int/long or a CPU register is a fixed slab of bits (32 or 64). Operations that exceed that range wrap around (modular arithmetic) or are undefined behavior for signed overflow — (1 << 63) << 1 quietly becomes 0. Python’s int has no such ceiling: 2 ** 1000 is an ordinary value, and 10 ** 100 is computed exactly. The trade-offs are direct consequences of the representation:

  • No overflow, ever — the digit array simply grows. This is why Python needs no separate BigInteger type (unlike Java’s long vs BigInteger or Go’s int64 vs math/big.Int).
  • Boxed, not unboxed — every int is a heap object with a header and reference count, so even 5 costs ~28 bytes and a pointer dereference. A machine int is just bits in a register. This is a major reason numeric-heavy Python leans on NumPy, which stores unboxed C integers in contiguous arrays.
  • Slower per operation for small values — even adding two small ints goes through type dispatch, the compact-int check, and re-boxing, where C does one instruction. The compact fast path narrows but does not close this gap.
  • Predictable, exact semantics — // and % follow consistent floor-division rules at any size, and there is no signed/unsigned confusion.

Common Misunderstandings

  • “int is 64-bit in Python.” No. There is no machine-word size limit; the only limit is memory. The “64-bit” intuition comes from C and from NumPy’s fixed-width dtypes.
  • “Digits are decimal or single bits.” Neither — they are base-2³⁰ “limbs.” Decimal rendering (str(n)) is a separate base-conversion step, and on CPython 3.14 there is even a configurable digit-limit (sys.set_int_max_str_digits) to bound the cost of converting astronomically large integers to/from decimal strings, a denial-of-service mitigation. (longobject.c)
  • “Small integers are special because of the layout.” The compact fast path (one digit) is a representation optimization for all small magnitudes. The singleton cache of −5..256 is a separate identity optimization — that’s why 256 is 256 but 1000 is 1000 may be False. See Small Integer and String Caching and Integer and String Identity Surprises.
  • “Karatsuba always helps.” Below 70 digits it loses to grade school because of recursion and allocation overhead — hence the cutoff. Karatsuba only pays off for genuinely large integers (hundreds of decimal digits).

Production Notes

The compact-int redesign that moved sign+size into lv_tag shipped in CPython 3.12 and is the layout you see in 3.14; it shrank the per-int overhead and simplified the arithmetic hot paths. The small-int singletons were made statically initialized and immortal (the bit 2 flag, pycore_global_objects_fini_generated.h enumerates the −5 .. +4 range around the zero index in checks), which removed per-interpreter allocation of those objects — relevant for sub-interpreter startup and the free-threaded build. (bpo-45953 / gh-30092)

Performance-sensitive code that does heavy big-integer work (cryptography, computer algebra) should be aware that Python’s int is correct but not state-of-the-art fast for enormous operands — CPython’s Karatsuba is far behind GMP’s Toom–Cook/FFT multiplication. Libraries like gmpy2 wrap GMP for that regime. For ordinary application code, the compact fast path makes everyday integer arithmetic perfectly serviceable.

See Also

Graph View

Backlinks