Dissecting Lemire’s nearly divisionless random

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.