flâneur

The radix 2^51 trick

chosenplaintext.ca · 2,263 words · saved by 1 readers

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

The radix 2^51 trick 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. 2 64 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 que

saved by

related reading