Generate random number from random bits

Question

So I have a function that gives me random bits rand(0,1) i want to generalize this to rand(a,b) that gives me a random number in the range a to b.

My idea is to just calculate the amount of bits in b - a and then append them together. I think this will work but it's not going to be uniform. I feel like it will favor larger numbers as opposed to smaller numbers(numbers closer to a). Not really asking for a straight up answer just some help would be nice.

EDIT: This is my idea so far, just not sure on the uniform part

    pseudo code:
    function rand_range(a, b):
        n = b - a
        sum = a
        for i in range(n):
            sum += rand(0,1)

        return sum

Answer 1

For a uniform distribution you need rejection sampling:

Lets say you want to generate numbers between 4,5,6 (inclusive), then 2 bits are sufficient. Mapping 00 -> 4, 01 -> 5, 10 -> 6, 11 -> reject

pseudo code:
function rand_range(a, b):
    n = ceil(log2(b - a))
    m = b-a

    while(true)
        sum = a
        bits = []
        for i in range(n):
            bits.append(rand(0,1))
        sum += ToBase10(bits)
        if sum <= b:
            break

    return sum

Answer 2

Yes, it's not going to be uniform.

Consider the simple case of 3 bits:

0+0+0  0
0+0+1  1
0+1+0  1
0+1+1  2
1+0+0  1
1+0+1  2
1+1+0  2
1+1+1  3

It's clear to see that 1 and 2 are more likely to occur than 0 or 3.

This gets a lot more non-uniform as you increase the number of bits - 0 and the maximum will never be able to occur more than once, the ones in the middle occur the most.

---

For a random distribution, the best I can think of involves throwing some generated numbers away.

Round b-a up to the closest power of 2 minus 1, then generate each bit individually and, if the result is greater than b-a, try again.

So, if b-a is 5, round up to 7, and generate the 3 bits involved to make a maximum number of 7:

000  0
001  1
010  2
011  3
100  4
101  5
110  6
111  7

Now, in the case of 6 or 7, throw them away and try again.

This can be done by using strings and concatenating a 0 or a 1, and converting to a number at the end, or, at each step, multiplying by 2 (as to shift all the bits one position to the left) and adding 0 or 1.

At the end you'll still add the result to a.

Answer 3

Well, not only the result is not random, but you can fail generate a value between (a,b) since it can so happen that rand(0,1) will always generate 0, hence yielding a number which is out of your range (if a>0).

The problem is there because let's say for a range (0,5), 0 will have only 1 representation being 00000 while 1 will have 5: 10000,01000,00100,00010,00001. Realizing this, the straight forward solution should be a bijective mapping, hence the easiest solution is to consider your 0 and 1 as bits of a number, because any number has a unique representation in base 2.

Hence the pseudo code:

const MAX_BITS = 9;
const MAX_VAL = 1023; 
fun rand_range(a,b){
    sum = 0;
    for i<MAX_BITS
        sum += pow(2,i)*rand(1,0)
    // rescale
    return (b-a) * sum/MAX_VAL + a

}

For MAX_BITS and MAX_VAL limits of your data type that will be input to rand_range() can be chosen so that you can guarantee that every input will be rescaled properly.

Answer 4

Think following is the better way to do it :-

1. find log2(b-a) (number of bits to represent b-a)
2. generate log2(b-a) bits at random and construct decimal number from it.
3. if number is greater than (b-a) reject it and repeat 2.
4. else evaluate a + rand(b-a).

Time Complexity :- If random number generator is truely random then you will take two iterations to get the random number in range b-a hence T(a,b) = log(b-a)

Here is java implementation :-

public class RNG {

    public static int rand(int a,int b) {
        int bits = 0;
        int diff = b-a;
        Random r = new Random();
        while(diff>0) {
            bits++;
            diff = diff/2;
        }
        while(true) {
            int acc = 0;
            for(int i=0;i<bits;i++) {
                acc = 2*acc +  r.nextInt(2);
            }
            if(acc<=b-a) {
                return(a+acc);
            }

        }

    }


    public static void main(String[] args) {

        int a = 150;
        int b = 300;
        int freq[] = new int[b+1];
        for(int i=0;i<1000;i++) {
          int k = rand(a,b);
          freq[k]++;

        }
        System.out.println("freq:");
        for(int j=a;j<=b;j++) {
            System.out.println(j+" : "+freq[j]);
        }
    }

}

Answer 5

In Python you could subclass random.Random class to get the full interface including randint(a, b).

import random

class Random(random.Random):
    def random(self):
        """Get the next random number in the range [0.0, 1.0)."""
        return self.getrandbits(53) * 2**-53
    def getrandbits(self, k):
        """getrandbits(k) -> x.  Generates an int with k random bits."""
        return sum(rand(0, 1) << r for r in range(k))

    def seed(self, *args, **kwargs): # unused methods
        return None
    def getstate(self, *args, **kwargs):
        raise NotImplementedError
    def setstate(self, *args, **kwargs):
        raise NotImplementedError

x = rand(a,b) can be expressed as r = Random(); x = r.randint(a, b)

The advantage is that if you define random(), getrandbits() methods correctly then the rest of the code is already tested and just works. _randbelow() method shows how these primitives could be used to return a random int in the range [0,n) that could be easily extended to define randint(a, b).