Read CPython's longobject.c: How Python Integers Work

Topic Overview

Arbitrary Precision Integers

Python integers are not fixed-width C `long` values. CPython stores them as `PyLongObject` with a digit array in base 2^30, defined in `longobject.c` and `longintrepr.h`.

Digit Limbs and Small-Int Cache

Each limb is a `digit` (typically `uint32`) but only 30 bits are used so multiplication of two digits never overflows a 64-bit intermediate. A number like 2^60 splits into limbs `[0, 1]` because 2^60 = 1 * 2^30 + 0.

CPython also caches integers from -5 to 256:

• `x = 5; y = 5; x is y` prints `True` because both names point at the same cached object
• Values outside the cache allocate a fresh `PyLongObject`

For example, 1234567890123 requires multiple 30-bit limbs when stored in little-endian order.

```c typedef struct { PyObject_HEAD ssize_t ob_size; digit ob_digit[1]; } PyLongObject; ```

Design Notes

Arbitrary precision is not free: every large integer operation allocates and may carry across limbs. Profile hot loops that accidentally promote small ints to big ints when values exceed the machine word.

For This Exercise

This exercise asks you to model `PyLongObject` layout in C. You will implement limb splitting for a 64-bit input and document the small-integer cache range that explains Python's identity quirks.

Your Task

Model CPython's PyLongObject. A Python int is stored as a sign plus a magnitude in base 2^30 digits, least significant first. The sign lives in ob_size: its absolute value is the digit count, and it is negative for negative numbers. Parse arbitrarily long decimal integers into this layout, print the layout, and implement + and * digit by digit, the way longobject.c does.

Input

One command per line:

cCopy
Loading…

The numbers are decimal integers with an optional sign and up to 200 digits.

Rules

• Layout: ob_size = ±digit count (0 for zero, and -0 is zero). Each digit is in 0..2^30-1, with no leading zero digits.
• Size: 24 + 4 × digits bytes (the CPython 3.11 header plus 4 bytes per digit).
• Small ints: values -5..256 are shared singletons. Append , cached small int.
• add: when the signs match, add the magnitudes and count the carries out of each digit. Otherwise subtract the smaller magnitude from the larger, count the borrows, and take the larger one's sign.
• mul: schoolbook multiplication, one digit product per (i, j) pair. The result is negative when exactly one operand is.
• A malformed number prints bad integer: X.

Output

cCopy
Loading…

Numbers are printed in canonical decimal: no plus sign, no leading zeros. Use 1 carry/1 borrow/1 digit product in the singular.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Store numbers as 30-bit digits, and do the arithmetic on those digits (with 64-bit intermediates for products). Never convert through a C long: the inputs overflow it.
2. Convert to decimal by repeatedly dividing the digit array by 10^9.

Hidden tests cover 30-digit operands, mixed-sign addition with borrows, results that cancel to zero, negative products, and malformed numbers.