The radix 2^51 trick

Summary

Faster addition and subtraction on modern CPUs Do you remember how to do long addition on paper? ¹¹ ¹ 6876 + 3406 ------ 10282 Starting from the “ones” position, we add 6 + 6 = 12, write down a 2 and carry a 1. We proceed to the left, one position at a time, until there are no more digits to add. When implementing addition for large integers (e.g. 264 and above), it’s common to write code that looks quite similar to this algorithm. Interestingly, there’s a straightforward trick that can speed up this process enormously on modern CPUs. But first, a question: why do we start long addition with the “ones”? Why not start on the left? The answer, of course, is the carries. We can’t figure out for sure what a given digit of the answer will be until we’ve completed all of the additions to the right of that digit. Imagine if we tried to add left-to-right instead: 6 + 3 = 9. So the first digit is 9. 8 + 4 = 12. OK, the second digit is 2… but carry a 1, so the first digit was actually 9 + 1 = 10… now carry back that 1… For mental math, this isn’t too bad (and some people actually prefer it when working with small enough numbers). As an algorithm, however, this approach has some fundamental limitations that become clear when working with larger numbers. Most importantly, because the later parts of the computation rely on information from the earlier parts of the computation, it’s hard to split up and parallelize the work. What about computers? Computers don’t work in base 10, of course. Instead, modern desktop and server CPUs expose an interface for operating on (for the most part) 64-bit integers. ; Add the 64-bit value in B to the 64-bit value in A add A, B ; Note: I'll use letters instead of real register names to keep things simple As long as our numbers fit within a single 64-bit value, things are easy. But what if we want to add, say, two 256-bit integers, x and y? The obvious solution would be to break up each 256-bit number into four 64-bit pieces (commonly referred to...