The radix 2^51 trick (2017)

The radix 2^51 trick 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 firs ... Read full article.