from Hacker News

Dissecting Lemire’s nearly divisionless random

by bbgm on 9/30/20, 9:48 PM with 1 comments

• by kwillets on 10/1/20, 1:37 AM

  Oops, I started on an entry for this, and then went off with some new variants on the algo and forgot my original goal.

  But I did make it fairly readable:

      FixedPoint<uint32_t> x;
      do {
        x.setFraction(src());
        x *= range;
      } while(isRejectedValue(x.fraction()));
  
      return x.floor();
  

  Basically all the weird casts and things in Lemire are parts of 32.32 fixed point arithmetic; we stuff a random value into the .32 part to make a number in [0,1) and multiply. The rejection condition is a bit of modular arithmetic but not super hard.

  https://github.com/KWillets/range_generator/blob/59ffea502c4...

  I added another method where it doesn't reject but extends right (variable-precision) until it's certain of the exact answer (ie that the floor() cannot change). I believe the Ryu printf algorithm does something similar to get the requested number of digits. It's unbiased but uses more random bits, which are expensive.