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.

Nice.

A pity it requires knowing sizes in advance. I wonder... Could you do something similar "afterwards"?

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.

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.

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.

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.