Okay, so this is a way to generate a sampling in order, so you don't have to keep a sorted list and your run time can be k instead of klogk. Mostly.
The body of the post, with its talk of strict timing and sample bias, had me thinking it had some clever way to pick a random number from 1 to n in finite time. But that's not actually possible to do with a random bit source and a non-power-of-two n. If this algorithm hits certain rare values it will re-sample the RNG.
>had me thinking it had some clever way to pick a random number from 1 to n in finite time. But that's not actually possible to do with a random bit source and a non-power-of-two n
I can sample 1-6 in finite time by rolling a die. I suppose you mean given a RNG in range 1-2^n, you cannot get a sample range non-power-of-two in fixed time.
However, you can sample in finite time with probability as high as you like, since the likelihood of another roll falls off exponentially. So if the odds of your machine quantum tunneling into a star is p, then you can make an algorithm that does your sampling with fixed time T with probability more than 1-p, making it perfectly usable.
in practice, resampling rand takes very, very little time. I use it all the time for uniform [0,n) queries. The avg number of rolls is for the most part like 1.1 or less.
For example, to sample 0-9 given a 32 bit full period generator, since 2^32 mod 10 is 6, only in 6 cases out of 2^32 cases do you need a second roll. This is common.
The body of the post, with its talk of strict timing and sample bias, had me thinking it had some clever way to pick a random number from 1 to n in finite time. But that's not actually possible to do with a random bit source and a non-power-of-two n. If this algorithm hits certain rare values it will re-sample the RNG.