Arbitrary-precision integers (std.bigint)

Status: Not implemented. This page compares ways to provide issue #481’s std.bigint and recommends one. It ships no module, compiler change or API. Scheduling belongs to B38. The current integer contract is numeric types; library operators are user-defined arithmetic operators.

Recommendation

Write std.bigint in Plenty, in three steps:

1. Plenty module. A BigInt with an inline i64 for small values and u64 limbs for large ones. Schoolbook and Karatsuba multiplication, Knuth division and divide-and-conquer radix conversion, ported from num-bigint (MIT OR Apache-2.0) with credit. Every allocation is an ordinary fallible Plenty allocation.
2. Compiler builtins for limb arithmetic. u64.widening_mul (Cranelift umulhi plus imul) and an add-with-carry form. The measured limb loop is 4.6× slower than Rust without them.
3. Optional native kernel, only if measured to pay. A runtime entry for large multiplication (Toom-3 or an FFT) that writes into an output and scratch slice the Plenty caller has already allocated. It allocates nothing itself, so it needs no allocation-failure handling. Write it in permissively licensed Rust; do not use malachite.

Malachite does not fit. On allocation failure it aborts the process. It is LGPL-3.0-only, and the runtime archive is statically linked into user executables. It adds 1.2 MB to every executable that uses it and 35 s to a clean build. Its multiplication beats the alternatives only above about 10⁴ bits, and only through its AVX2 FFT on x86-64; the portable path was slower than every other crate, and ARM64 was not measured. It also parses decimal text 2–6× faster.

Requirements

• Fallible allocation. Every allocation in std reports AllocError; a Rust allocation failure in the runtime aborts the process (Rust panics).
• License. Plenty is MIT OR Apache-2.0. No current dependency is used under a copyleft license. The only license expressions that mention LGPL also offer MIT OR Apache-2.0.
• Size and build cost. Code in the runtime archive costs nothing to programs that do not reach it, but grows the compiler and its build. The engine criteria move a module out of the archive above 2 MB per program or one minute of build time.
• Platforms. Linux x86-64 and ARM64, macOS ARM64, Windows x86-64 MSVC (cross-platform assessment).
• Project preference. Implement in Plenty unless native complexity or security justifies a wrapper (B38, AGENTS.md).

Allocation failure in candidate crates

Each crate’s source was read and run with a global allocator that refuses allocations over 4 KiB, then asked to square a 65,536-bit number.

No crate exposes an allocator parameter or a fallible API. Malachite’s limb-level functions with caller-supplied scratch, such as limbs_mul_greater_to_out, are crate-private unless the test_build feature is enabled, and its FFT path allocates regardless.

Can the runtime’s arena catch the abort?

The runtime can already contain one infallible Rust library: ring’s RSA operations run inside actor_heap::within with a pre-reserved arena. An allocation failure there jumps back and reports AllocError (RSA allocation). Applying this to malachite would fail for these reasons:

• Platforms. The arena router exists only on Linux x86-64 and ARM64. On other targets within runs the job directly and a failure aborts.
• Value-dependent memory. ring uses a fixed amount of memory per operation, so its arena has a fixed, tested size. A bignum operation’s memory grows with its operands (the FFT path uses O(n log n)), so each call must estimate a bound and reserve it first.
• Results cannot leave the arena. within forbids handing back allocations. Every result Natural would have to be copied into Plenty storage before the arena is freed: an extra O(n) copy and twice the peak memory.
• dashu panics instead of calling the allocation-error handler, so the arena cannot catch its failures at all.

An engine (shared library) does not help either: Rust’s Vec aborts there too, and the linalg engine reports allocation failure only because it uses fallible faer APIs and a fork. Forking malachite (about 650,000 lines with malachite-base) to make it fallible is not maintainable.

License: LGPL-3.0 in a statically linked runtime

The runtime archive, including any Rust crate it wraps, is statically linked into each executable that reaches the module. Under LGPL-3.0 §4, everyone who distributes such an executable conveys a “Combined Work” and must:

• give prominent notice and ship the GPL-3.0 and LGPL-3.0 texts;
• use terms that do not restrict modification of the library or reverse engineering to debug such modifications;
• either supply the application in a form the recipient can relink with a modified malachite (object files or source), or load malachite through a shared-library mechanism;
• for “User Products”, supply installation information.

These obligations fall on every Plenty user who distributes a binary that uses std.bigint, not only on the Plenty project. Relinking is also hard in practice: the Rust code is monomorphized and inlined into the runtime archive, so the user would need the whole runtime archive rebuilt against the modified malachite. A shared engine (libplenty_bigint_v1.so) would meet the relinking condition with §4(d)(1), but it still leaves the allocation-failure problem, costs a dynamic call per operation and must be shipped with the application. GMP/rug raises the same issues. GMP also needs m4 and make to build and does not support Windows MSVC (MSYS2/MinGW only).

num-bigint, ibig and dashu are MIT OR Apache-2.0, so their algorithms can be ported into Plenty with credit in the module header and its ## Acknowledgements section.

Measurements

Measured 2026-10-31 on an AMD Ryzen 7 7840HS, rustc 1.99.1, release build with panic=abort and codegen-units=1, pinned to one core. Inputs are pseudo-random. The scratch crate lives under the worktree’s target/ directory and is not committed.

Throughput

Nanoseconds per operation. “Small” is 10 million &a + &b or &a * &b on values that fit in a word, producing a new value each time.

Malachite is 2.4–6× faster at 65,536 bits and above, and much faster at parsing. Up to 4,096 bits and on small values it is no faster than the others. Its large-size speed comes from an f64 FFT that uses AVX2 and FMA only when the std feature enables runtime CPU detection. With default-features = false (the portable path), 65,536-bit multiplication took 837,473 ns, slower than every other crate. The ARM64 path uses the wide crate and was not measured.

Plenty limb arithmetic

The same schoolbook multiplication was written in Plenty, compiled with --release. Plenty has no u128 or high-half multiply, so each 64×64-bit product uses four 32-bit multiplies. The Rust baseline uses u128.

The inlined inner loop costs 5.5 ns per limb product against Rust’s 1.2 ns. The small-size cost is mostly fixed overhead: allocating and filling the result list and the call. Holding 32-bit limbs in u64 slots, so that each product needs one multiply, was slower (43,463 ns at 4,096 bits). The remaining cost is in the checked adds and the indexing, not the multiply. A widening-multiply builtin and a carry form would remove the emulation and most of the overflow checks.

A Plenty small-value fast path is as fast as the crates’ small paths: enum Big: Small(i64) | Large(list[u64]) with an __add__ hook that tries a checked: add takes 8.7 ns per (acc + one)?. Calling a native crate would add a call into the runtime and an owned native handle per result, on top of the crate’s own 6–8 ns.

Executable size and build time

The program parses one number, squares it and prints it. Sizes are of a stripped Rust executable; the baseline prints its argument.

Malachite would remain under the 2 MB engine threshold. Its build time would use more than half of the one-minute budget, and every compiler build would pay it. A Plenty module adds only the functions a program reaches; it needs no Rust build.

Options compared

API direction

These signatures are a sketch for the implementation PR to settle.

from std.bigint import BigInt

class BigInt            # not a copy class; copy(x)? duplicates the limbs
    def __add__(self, other: &BigInt) -> Result[BigInt, AllocError]
    def __radd__(self, other: i64) -> Result[BigInt, AllocError]  # i64 + BigInt
    def __sub__, __mul__, __floordiv__, __mod__, __neg__, __lshift__, __rshift__,
        __and__, __or__, __xor__   # same shape
    def add_assign(self: &mut BigInt, other: &BigInt) -> Result[(), AllocError]
    def cmp(self, other: &BigInt) -> i64          # until __cmp__ (B37)
    def to_i64(self) -> Result[i64, RangeError]
    def to_f64(self) -> f64
    def display[W](self, out: &mut Formatter[W]) -> Result[(), FormatError]
    def to_str(self, radix: i64) -> Result[str, AllocError]
def from_i64(value: i64) -> BigInt                # no allocation
def parse(text: &str, radix: i64) -> Result[BigInt, ParseError | AllocError]

• Ownership. Operator hooks take a shared self and a shared or copyable operand, and return an owned result. a + b borrows both operands and never consumes them. A result that fits in i64 is stored inline and allocates nothing, but the hook still returns Result, so callers write (a + b)?.
• In-place operators. __iadd__ must return (), so it cannot report AllocError. Provide named fallible methods (add_assign) instead, which is the reference’s own advice (“use explicit assignment or a named fallible method”).
• Division. Use floor semantics, as // and % have on i64. A zero divisor traps, as it does for i64. A checked variant can return ZeroDivisionError.
• Equality and ordering. == is structural, so it is correct only if the representation is canonical. Every value that fits in i64 is Small, and limbs carry no high zeros. Classes have no ordering operators until the user-defined ordering proposal’s __cmp__ lands, so cmp is a method for now. BigInt cannot be a dictionary key until user-type hashing lands.
• Limits. Text conversion of attacker-controlled input should either use subquadratic algorithms or take a digit limit, like other parsers’ Limits.

Open questions

• BigInt + i64. Each operator has one left hook, so __add__ cannot accept both &BigInt and i64. i64 + BigInt works through __radd__. For the other order, callers write a + from_i64(n), which allocates nothing, unless hooks gain overloading or a mixed-operand sum type.
• Names and signatures of the limb builtins (widening_mul -> (u64, u64), carrying_add(other, carry: bool) -> (u64, bool)), and whether Cranelift lowers them on ARM64 as cheaply as on x86-64.
• The size threshold above which a native multiplication kernel is worth its code, measured after the builtins land.
• Whether small helper functions in the limb loop need inlining. The measured call to mul_wide cost 1.5× in the 4,096-bit loop.

Acknowledgements

• num-bigint (MIT OR Apache-2.0): the reference implementation suggested by issue #481; the recommended source for ported algorithms.
• malachite (LGPL-3.0-only), ibig and dashu (MIT OR Apache-2.0), and GMP (LGPL-3.0 or GPL-2.0): evaluated and measured here; no code is used.