5 ms·
Take the interval [0, 1), keep cutting it in half and picking a side, until the interval's contained by a [k/n, (k+1)/n). Consider your case where n = 129. Af
by SamReidHughes 12y ago
Take the interval [0, 1), keep cutting it in half and picking a side, until the interval's contained by a [k/n, (k+1)/n).
Consider your case where n = 129. After 8 subdivisions, you have 256 possible intervals, which means the 128 interior boundary points (numbers of the from k/129, 0 < k < 129) will lie within half of the intervals, and the other half has definitively chosen a number. Those which haven't have a 50% chance of terminating after each successive bit, so you've got on average 9 bits of entropy per call.
I don't know if that's optimal, but you can't do better than 8.
- TheLoneWolfling 12y agoYou can do better than 8, as mark-r said. Do as I mentioned, but batch requests. For example, if you generate 89 numbers from 0-128 inclusive at once, you'll need, on average, 624.3 bits of entropy to generate them, whereas the optimal is 624.0 bits. That's an average of 7.0 bits of entropy per number generated. (It works out to something like 1.00054 x optimal.) So, generate a number from 0 to 128^k-1, and split it base 129, for some value of k, returning the k random numbers generated this way. For sufficiently large k you will be able to use arbitrarily close to the optimal number of bits of entropy per request. Unfortunately, this requires you know in advance what the range of the random numbers to generate will be.
- SamReidHughes 12y agoYou don't need to know in advance. Generate a big r from 0 <= r < s. When calling randint(n), return r mod n and update (r, s) = (r/n, s/n), unless r >= s - (s mod n) in which case reset s and regenerate r.