Radix 2^51 limbs beat add-with-carry chains by deferring carries

Adding numbers wider than 64 bits should be easy: split each 256-bit integer into four 64-bit pieces, add them, and propagate any overflow upward. The catch is the overflow — without carries the answer is wrong, so the correct version chains x86's add-with-carry instruction (adc) from the least-significant limb up. On modern out-of-order CPUs that chain is slower than the incorrect parallel code: adc is a heavier instruction, and each one depends on the carry flag produced by the previous one. A Haswell CPU can issue up to four independent adds per cycle, but chained adcs execute serially.

The counterintuitive fix, known in the cryptography literature as radix 2^51 representation, is to use more limbs that are each smaller than a register. Where the obvious approach splits 256 bits into four base-2^64 digits, this approach splits it into five base-2^51 digits; each 64-bit limb still holds its digit, but the top 12–13 bits stay empty as space where carries can accumulate. Because of that headroom, adding normalized values produces no carry at all until the spare bits fill — up to roughly 2^13 additions — so every add is independent and the processor schedules them in parallel.

Carries are not eliminated, only deferred. When headroom runs out, one normalization pass shifts each limb's overflow into the limb above and clears the slack, and subtraction works the same way by treating limbs as signed, at the cost of one headroom bit. The author's quick benchmarks on a Haswell machine found radix-2^51 addition already faster than radix-2^64 addition for as few as three additions, including the cost of converting into and out of the representation, with the saving growing as more additions accumulate.

The post builds the intuition on paper first: in base 10, widening each digit's range so it can count past 9 lets several normalized numbers be added before any digit overflows, and one normalization pass converts the result back. Moved to binary registers, the same principle is why the representation is standard in cryptography — and why, counterintuitively, spreading a number across more registers and issuing more instructions makes the arithmetic faster. First published in 2017, the article was posted to Hacker News in May 2020 and drew 518 points and 83 comments.

Shrink limbs to 51 bits so spare bits absorb carries: adds stay independent and parallel, and normalization happens once at the end

Carries are the dependency: chained adc instructions serialize because each waits on the previous carry flag, while independent plain adds can issue four per cycle on Haswell.

Empty headroom is the trick: 51-bit digits inside 64-bit registers leave 12–13 bits free, so roughly 2^13 additions happen before any carry must propagate.

One deferred pass beats many immediate ones: normalization at the end is a fixed sweep instead of a carry dependency on every operation.

The extra limb pays for itself: five plain adds beat four adc chains from as few as three additions, even counting conversion cost.

To break a serial dependency, add slack you pay back later: reserve headroom so the hot operation runs free, then settle the deferred work in one pass.

Published in 2017 and posted to Hacker News in May 2020, it drew 518 points and 83 comments. Practitioners anchored the trick to real code: commenters noted Curve25519's field arithmetic works modulo 2^255−19, so values fit 51-bit limbs, with a radix-2^25.5 variant on 32-bit CPUs; others debated Broadwell's ADCX/ADOX instructions and partial-register stalls, and one flagged an error in the article's explanation of the top limb. The technique remained what the post called it: a standard radix-2^51 representation in cryptography, used where field arithmetic must be fast and constant-time.