# Make isc_random_uniform() nearly divisionless

It used to require two 32-bit integer divisions to get a random number less than some limit. Now we use Daniel Lemire's "nearly-divisionless" algorithm for unbiased bounded random numbers, which requires one 64-bit integer multiply in the usual case, and one 32-bit integer division in rare slow cases. Even the slow cases are faster than before; there are also fewer branches.

I think this algorithm is exceptionally beautiful. It also has more clever tricks than lines of code, so I have done my best to explain how it works.

It is possible to go further and get bounded random numbers with no divisions at all. However, this can only save time in the slow path which is taken very rarely, so the wins from avoiding the remaining divisions are swamped by the losses from the greater code complexity.