2 ms·

Great explanation. A couple of things. So in C -s == 2⁶⁴ - s ? That seems very strange! Also, there's still a modulo in there, (-s) % s; does the compil

Great explanation. A couple of things. So in C -s == 2⁶⁴ - s ? That seems very strange! Also, there's still a modulo in there, (-s) % s; does the compiler not use a division for that line or something?

BeeOnRope 6y ago
> 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.
- Someone 6y ago
  But the price you pay is having input values that are a lot wider than you need, so you waste random input bits. Generating those can be costly, too.
  - BeeOnRope 6y ago
    Yes, although it doesn't necessarily have to be "a lot". E.g., if you want random values between 1 and 1,000,000 that takes ~20 bits of entropy, but if you use 25 bits and Lemire's technique you'll be running at almost full speed because of the 5 extra bits (you fall into the slow case about 3% of the time).
TTPrograms 6y ago
That's called "Two's Complement" - here for 64 bit integers. https://en.wikipedia.org/wiki/Two%27s_complement https://en.wikipedia.org/wiki/Two%27s_complement Say x = (2^64 - s) in a 64 bit integer. Then (x + s) = 2^64 = 0 (as 2^64 rolls over to 0). So for the purposes of addition etc. you can say -s = 2^64 - s.
- BeeOnRope 6y ago
  Lemire (and the article) are generally using unsigned values in their examples, so I don't think two's complement matters much here: just the even simpler "non-negative arithmetic modulo M".

BeeOnRope 6y ago

> 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.

Someone 6y ago
But the price you pay is having input values that are a lot wider than you need, so you waste random input bits. Generating those can be costly, too.
- BeeOnRope 6y ago
  Yes, although it doesn't necessarily have to be "a lot". E.g., if you want random values between 1 and 1,000,000 that takes ~20 bits of entropy, but if you use 25 bits and Lemire's technique you'll be running at almost full speed because of the 5 extra bits (you fall into the slow case about 3% of the time).

TTPrograms 6y ago

That's called "Two's Complement" - here for 64 bit integers. https://en.wikipedia.org/wiki/Two%27s_complement https://en.wikipedia.org/wiki/Two%27s_complement Say x = (2^64 - s) in a 64 bit integer. Then (x + s) = 2^64 = 0 (as 2^64 rolls over to 0). So for the purposes of addition etc. you can say -s = 2^64 - s.

BeeOnRope 6y ago
Lemire (and the article) are generally using unsigned values in their examples, so I don't think two's complement matters much here: just the even simpler "non-negative arithmetic modulo M".