Get the latest tech news
The radix 2^51 trick (2017)
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.
Combine that with the fact that Haswell processors can execute two vpaddq s per cycle, and you can see that we’re taking a serious performance hit in order to handle carries properly. In radix 2 51 representation, 2 64 digits allow us to add up to 2 13 normalized numbers before we need to worry about the high 13 bits overflowing. For our purposes, we’re going to ignore the carries in the most significant limb, allowing numbers to wrap when they overflow past 2 256- 1 (just like how unsigned addition works in C with normal size integer types).
Or read this on Hacker News
