> That seems very strange! One way of thinking about it is that in arithmetic modulo M you can add or subtract any number of M terms without changing the resul

> That seems very strange! One way of thinking about it is that in arithmetic modulo M you can add or subtract any number of M terms without changing the result. So x and M + x and 2M + x are all the same. So 2^64 - s is the same as 2^64 - s - 2^64 = -s. > Also, there's still a modulo in there Yes, but it is guarded by the earlier check, so is executed only rarely (very rarely for most moderate range values << 2^64). IMO this is half of key insight that makes Lemire's approach fast: that the modulo can be avoided most of the time by the coarser check and for wide (e.g., 2^64) input values, this means the modulo might as well not exist, performance-wise.