Part of Familiars: the small, sharp libraries I carved out of Xapiand. This one has no ceiling: uinteger_t, an integer as big as memory allows, which I grew in 2017 out of Jason Lee’s uint128_t.
Sixty-four bits is a lot of headroom until it isn’t. A hash wider than a machine word, a base-62 id, a factorial, a counter that must never silently wrap: all of them run past uint64_t, and when they do you want a number that keeps going, without giving up the thing that makes integers pleasant, which is that they read like arithmetic. a * b + c, not bignum_add(bignum_mul(a, b), c).
uinteger_t is that number: a single-header arbitrary-precision unsigned integer that behaves like a built-in one. You build it from a native integer, raw bytes, or a string in any base from 2 to 36, do the usual arithmetic, bitwise, shift, and comparison operations, and render it back out in whatever base you like. Inside, the value is a run of 64-bit limbs in little-endian order.
The easy two thirds
Section titled “The easy two thirds”Two of the four operations are almost free. Addition and subtraction are the grade-school algorithm on 64-bit limbs: walk the limbs low to high, add with a carry, subtract with a borrow. Nothing subtle.
Multiplication starts as the grade-school algorithm too, long multiplication, limb by limb, which is O(n²). That is fine until the numbers get big, at which point uinteger_t switches to Karatsuba, the classic divide-and-conquer trick: split each number into a high and low half, and notice that the four half-products a naive split needs can be computed from only three multiplications plus some additions. Recurse, and O(n²) becomes about O(n^1.585). It is one of the first algorithms that makes you feel the difference between “correct” and “fast,” and the crossover point, where small numbers stay long and big numbers go Karatsuba, is where the tuning starts.
Karatsuba is only the first rung. As the numbers keep growing, uinteger_t moves on to Toom-3 and Toom-4, the same trick with each number cut into three or four pieces instead of two, and at the top, for numbers thousands of limbs long, to a number-theoretic transform: the FFT idea of turning a multiplication into many small independent ones, done in exact integer arithmetic so no rounding ever creeps in. Squaring a number gets its own path at every rung, since a * a has symmetry a general product does not.
The operation everyone gets wrong
Section titled “The operation everyone gets wrong”And then there is division, which is where bignum libraries go to die.
Long division of large numbers is the hardest of the four basic operations by a wide margin, and the foundation is Knuth’s Algorithm D, from The Art of Computer Programming, volume 2. It looks like the long division you learned, but every step hides a trap. You normalize first, shifting both operands so the divisor’s top limb has its high bit set, because the whole thing only works when the leading limb is large enough. Then, for each output digit, you estimate the quotient digit from just the top two limbs of the running remainder and the top limb of the divisor, an estimate that is provably at most two too high. And then the part that everyone skips: sometimes the estimate is still one too high after you correct it once, and you have to add the divisor back and decrement the digit.
That add-back fires rarely, on the order of once in every 2 to the 63rd, which is exactly what makes it dangerous. Leave it out and your bignum division passes every test you will ever bother to write, ships, and then produces a wrong quotient for some input nobody tried, silently, with no crash to tell you where. Getting Algorithm D entirely right, normalization, the two-limb estimate, and the add-back you will never see fire, is the difference between a bignum you can trust and a landmine. It is the reason a “simple” arbitrary-precision integer is not simple at all.
Algorithm D is the base case in uinteger_t, not the whole story. Its quotient-digit estimate comes from the divisor’s top two limbs and a precomputed reciprocal of them, a multiply instead of a slow hardware divide, and it is always exact or one too high, so at most one add-back follows. From 2,048-bit divisors, a recursive method (Burnikel-Ziegler) splits one huge division into smaller ones that bottom out in Algorithm D again, so the add-back still has to be right. And for the giants, a divisor of 1,400 limbs and a quotient of 5,000, it computes an approximate reciprocal of the whole divisor with Newton’s iteration and multiplies by it, which hands the work to the fast multiplication above.
Where it fits
Section titled “Where it fits”Reach for it when you need exact integer math past 64 bits and you want a small header-only dependency that reads like ordinary integer code: big hashes, cryptographic-sized values, base conversions, counters that must never wrap. Skip it when a fixed-width type (uint64_t, __int128) already covers your range, or when you need signed values, rationals, or modular arithmetic. It is unsigned only, and with no fixed width there is nothing to overflow, so subtraction below zero wraps the way unsigned always does.
The base-conversion corner even grew a sibling. The built-in 2 to 36 handles the plain digit alphabets; when you want the encoding side of that idea, arbitrary alphabets and the human-friendly bases past 36, that is base-x. It stacks straight on top of uinteger_t, treating a byte buffer as one big unsigned integer and rewriting it in whatever alphabet you hand it: base58, base62, Bitcoin, Ripple, Crockford, with optional check digits and checksums for ids people copy and type by hand. The base-62 id from the opening of this post is one of its jobs.
The next familiar goes back into the running server and does something that sounds wasteful and is precisely the opposite: it arms a log line on every single operation, and throws almost all of them away.