3 ms·

Here's a simpler, but more technical, attempt at an explanation. --- while (true) { Treat your initial 64 bit random value as a fixed point fraction in t

Here's a simpler, but more technical, attempt at an explanation. --- while (true) { Treat your initial 64 bit random value as a fixed point fraction in the range from 0 to just under 1. u64 fract = random64(); Convert it to a 128 bit type, still treating it as a fraction, and multiply it by another 64-bit nonzero integer, S. The result is a value between 0 and S (excluding S), with the fractional part in the lower 64 bits and the integer part in the upper 64 bits. u128 upto_s = (u128)fract * (u128)s; u64 fract_part = (u64)upto_s; u64 int_part = (u64)(upto_s >> 64); Because we multiplied by S, the possible resulting fraction bits increase by S between each sequential random value. This affects the number of possible fractions for each integer part. For example, with S=3, you could pack like . X . . X . . X . . X . . X . . or X . . X . . X . . X . . X . . X This is NOT the case if the number of possible fractions (here 2⁶⁴) is a multiple of S. We can therefore reject some of our possible fractions to make it a multiple of S. This can be done by rejecting the first 2⁶⁴ % s fractional values, and thus only accepting fractional values at least 2⁶⁴ % s. # Faster early test to avoid modulo # s > (2⁶⁴) % s if (fract_part >= s) { return int_part; } # 2⁶⁴ % s == (2⁶⁴ - s) % s == (-s) % s u64 min_fract = (-s) % s; if (fract_part >= min_fract) { return int_part; } }

javajosh 6y ago
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".

javajosh 6y ago

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