How to generate random numbers within a range (0,n) from random bits?

What is a good method to generate random numbers between 0 and n from random bits?

For example, I have a one million random bits generated according to NIST SP 800 90 publications. Now I need to generate random numbers between 0 and 100 (inclusive) using these random bits. Few possible methods i could think of are

Read 7 bits, convert these to a number (0 to 127), store the number if its <= 100, otherwise :-

• discard and move to next 7 bits e.g bits = 1111111, discard
• take module 101 and store the number e.g bits = 1111111, store 26
• remove most significant bit and store the number e.g bits = 1111111, store 63
• left shift 1 bit position, read next bit and store if <=100, otherwise again left shit 1 bit position and read next bit e.g bits = 1100011, left shift 1 bit=110001, assume next bit 0, then bits = 1100010; store 98

I think discarding and regenerating if the result is > 100 is the best solution. Although you may have the problem that computation time varies, which could lead to side-channel attacks in a given context.

Computing modulo 100 gives every number from 0 to 27 a higher probability than the numbers 28 to 100... and I don't quite understand why you compute modulo 100 and not modulo 101 if 100 should be included.

By removing the first element, you have the same problem for all numbers from 0 to 63.

I think you have the same problem for the last method, but with a more complex set of numbers which are more likely.

An idea I had: You could create a data structure, e.g. a tree, in which you do a random search. The problem I see is that you have 101 elements, which makes it quite tricky.

Posting this as an answer because nobody else cited this paper yet. In https://arxiv.org/pdf/1304.1916.pdf (Optimal Discrete Uniform Generation from Coin Flips, and Applications by Jérémie Lumbroso) we can read:

This article introduces an algorithm to draw random discrete uniform variables within a given range of size n from a source of random bits.

Below is the main algorithm reproduced.

Yep, just drop anything > 100 after having stacked seven bits.

You'll forfeit $\approx$ 21% of the available sequence, but such sequences come quickly and easily, and the unequivocal non bias outweighs the loss. You should be able to convince yourself of living with a 79% generation efficiency to get valid random numbers.

And part of that convincing comes from some of the other answers and comments thereto. Alternative generators (even if more efficacious) mean more code that has to be debugged. Also what has not been mentioned is testing. Rejection sampling is self evidently unbiased. It just works if a bit wasteful. Call that overhead insurance.

Alternative and more complex techniques will have to be tested. How? Ideally you'd perform a randomness test on the output set. Unfortunately there is no test suite that can handle an input range $0 - n, n \ne 255$. Even a mono-bit test will fail as the number of ones and zeros is meant to be uneven in this particular example, and is further confounded by Chi variation. So self designed tests become necessary. And how do you test the tests? You'd generate a reference sequence from something like $\pi$ or $e$ binary expansions, having rejection sampled them for certainly ↺

Rejection sample. It just works.

What is a good method to generate random numbers between 0 and n from random bits?

There are a number of known methods to convert a stream of random bits into an integer within a range; which ones are "good" would depend on what good is:

• Simple to program
• Have no bias (versus having a bias that's within a proscribed bound)
• Minimize the expected number of random bits used
• Have a bound on the number of random bits used
• Not infinite loop if given a stream of bits that aren't random (e.g. all 1's).

Of course, some of these goals are in conflict (for example, "no bias" and "bounded number of bits used" cannot both be achieved if the size of the range isn't a power of 2).

If the main goal is simplicity (and reducing the likelihood of getting something wrong), then a straight-forward 'grab 7 bits, check if those 7 bits converted to an integer is in range, if not, try again' is good (and 'grabbing 8, discard one and then check' may be even simpler if you're in a byte-oriented environment).

On the other hand, if it is important to minimize the number of random bits used (and be unbiased), then this procedure happens to be optimal over systems that don't preserve internal state between invocations:

r := 1
a := 0
for (;;)
    a := 2*a + next_random_bit()
    r := 2*r
    if r >= 101
        if a < 101
           return a
        a := a - 101
        r := r - 101

This uses fewer than 7.5 random bits on average per element generated (which is more than 1 random bit less than the simple 'get 7 bits, reject if out of range' method).

If you want to keep to NIST recommendations then there are the NIST algorithms in NIST SP-800 90Ar1 section A.5 "Converting Random Bits into a Random Number" (the standard that is used in the question as source for a DRBG).

The method described in the question seems similar to the "Complex Discard Method" in section A.5.2 of the NIST document. It has the disadvantage that you have to perform modular calculations, but that's fine if your $n$ is a small number like $101$. It may not be something what you want if you have an $n$ of, say, 4096 bits as for e.g. RSA-KEM though.

In general you may want to use my own solution (which I hope is at least somewhat original) called RNG-BC (random number generation using binary compare) which is very efficient while not using any big integer calculations.

I'll quickly explain the method. Let's say that a value $x$ in the range $[0, n)$ needs to be drawn. During a compare only the topmost bits of the random number $x$ are compared to $n$. If the bit in $x$ is 0 and the bit at the same position in $n$ is 1 then the number is lower and the value is accepted. If it is equal then we need to look at the next bit, and the bit in $x$ is 1 and the bit in $n$ is zero then $x$ is higher, and we need to regenerate all the bits that we've looked at. As the lower bits of $x$ are never evaluated they do not need to be replaced.

This method draws about 1.7 more bits than the bits in $n$ (obviously depending on the value of $n$), and doesn't use any special calculations, although it may require some bit buffering. There is more information and an implementation here.

Disadvantages:

• the method isn't bounded to the number of bits it may consume. Since every bit has about half of a chance to be accepted that doesn't matter much. After about 128 bits the chances of it failing are only somewhat higher than 1 in $2^{128}$.
• The method doesn't store any state if you need multiple random values (in the same range), so it is not optimal if you want to generate many random numbers. With just 1.7 bits of overhead that point may be moot.

The method of just discarding the numbers outside the range is the method that is, simple, easy to prove correct, adaptable, least susceptible to subtle errors, and the one you should use.

For all practical purposes, stop reading, and go to this answer and embrace its contents

What if you do want to waste as few of those bits as possible though?

What you have then is the opposite problem of an entropy coder. An entropy coder takes numbers following some statistical distribution, and turns them into a stream of bits with as close to 1 bit of entropy per bit as possible. You have a stream of 1 bit of entropy per bit, and want to turn it into numbers with some distribution, the opposite operation.

That's what the decoding part of an entropy coding scheme does.

So what you would do is do the decoding stage of arithmetic coding, give it a statistical distribution of equal weights in the range 0-100, and feed it random bits as an input instead of an encoded file.

An arithmetic coder with 31-bit symbol tables should give you a waste fraction of $\approx 2 \cdot 10^{-8}$, at which point the 32 bits of warmup padding would be the greatest source of waste for your 1 million bits.

This is not a good idea in practice:

While this conversion is reasonably fast due to entropy coders being used in performance critical software like video encoding, this speed is very often a compromise originating from the entropy coders leaking entropy in all kind of little ways.

• This if fine for compression. Getting files a few bits larger than optimality is no big deal if decompression is quicker.
• This is absolutely not fine for crypto! Getting subtly skewed distributions would be fatal.

I have seen non-leaky arithmetic coders, in an academic setting, maybe once or twice. I have seen dozens more leaking, both intentionally (performance) or unintentionally.

I'll answer from the standpoint of seeking maximum performance.

Algorithm 5 of this paper is performs really well and is bias- and division-free (divisions might create a timing side channel). You can tune the parameter $L$ to consume more bits per input, while reducing the chance of a rejection.

For instance, for $L = 10$, the chance of rejection should be only $1 - 1010/1024 \approx 1.4\%$. You can quickly make three 10-bit words out of a 32 bit word by shifting and bitmasking. This wastes about 12 out of every 32 bits, or 37.5% of all bits, but also results in a low rejection rate, which translates into fewer of those costly mispredicted branches on the CPU, which result in pipeline flushes.

Note that any branch prediction scheme will necessarily fail on a rejection sampling algorithm, otherwise your bits wouldn't really be random at all. The best you can hope for, on the simple rejection scheme with 7 bits, is that the CPU always predicts "no rejection" and fails $1 - 101/128 \approx 21.1\%$ of the time. This results in a pipeline flush every 4-5 iterations, which may perform worse than the scheme suggested above. If the branch predictor tries to get too smart, mispredicted branches might happen even more often.

Do note, however, that a Monte Carlo simulation suggests you'll need $\approx 22\%$ more bits using my suggested parameters versus the simple 7-bit rejection scheme, so you'll have to balance the cost of generating these extra bits versus the cost of mispredicted branches.