4 ms·

A related question: Is there any efficient way to generate a random number in a range w.r.t. the amount of entropy used? The way I know (generate a random numb

A related question: Is there any efficient way to generate a random number in a range w.r.t. the amount of entropy used? The way I know (generate a random number, if it's in the top incomplete section regenerate until it isn't, modulo the width of the range, add the starting value - there are some fencepost errors here but you get the idea) is really inefficient in the case of, for example, you want a number between zero and half the range + 1 (so, for example, if you have an 8-bit RNG and you want numbers between 0-128, inclusive.) You end up using, on average, 8*(1/(1-127/256)) ~= 15.9 bits of entropy per call, whereas you only "need" to use log2(129) ~= 7.0 bits of entropy per call.

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 ago
  You 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 ago
    You 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.
mark-r 12y ago
Sometimes you can generate the random numbers in batches to get better efficiency. For your example, you can combine 3 random 8-bit values into a 24 bit value. You still only get 3 outputs, but you can use all the random values up to 7 * (129^3) - you only need regenerate random numbers 10% of the time, rather than 49%. 60 bits does even better, giving you 8 outputs and requiring regeneration only 0.2% of the time.
- TheLoneWolfling 12y ago
  Nice. A pity it requires knowing sizes in advance. I wonder... Could you do something similar "afterwards"?
  - mark-r 12y ago
    Sure you can, I used a short program myself to calculate the best case outcomes. The question is whether it would be worth the bother. Usually the range you request is much smaller than the range of your random number generator, so the number of regenerations required are nowhere near the worst case - and the cost of generating a random number isn't enough to get worried about.

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 ago
You 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 ago
  You 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.

mark-r 12y ago

Sometimes you can generate the random numbers in batches to get better efficiency. For your example, you can combine 3 random 8-bit values into a 24 bit value. You still only get 3 outputs, but you can use all the random values up to 7 * (129^3) - you only need regenerate random numbers 10% of the time, rather than 49%. 60 bits does even better, giving you 8 outputs and requiring regeneration only 0.2% of the time.

TheLoneWolfling 12y ago
Nice. A pity it requires knowing sizes in advance. I wonder... Could you do something similar "afterwards"?
- mark-r 12y ago
  Sure you can, I used a short program myself to calculate the best case outcomes. The question is whether it would be worth the bother. Usually the range you request is much smaller than the range of your random number generator, so the number of regenerations required are nowhere near the worst case - and the cost of generating a random number isn't enough to get worried about.