Generate randN given rand1

Given a rand1 that can generate 0 and 1 randomly, create a function randN that generate random number between 0 and n.

Lets start from base case, assume n = 3, and we are looking to generate a number uniformly distributed of 0 and 3, we could do rand1*2, which gives us a random distribution of 0 and 2, then we use rand1*2 + rand1, gives us a uniformly distribution of 0, 1, 2, and 3.

How about n = 4? rand1*4 gives us a uniformly distribution of 0 and 4, since we already have rand3 which generates a random number between 0 and 3, we could simply add rand1*4 + rand3(), which will give us a uniformly distribution of 0 ~ 7. and we simply pick those numbers less or equals than 4 (or try again according to uniformly distrubution idea)

See where the trend goes? we will have rand1 * 1, rand1 * 2, rand1 * 3 … plus some random number, which is the same as generating the binary representation of the number n. If the generated number is larger that n, we simply try again until we get the correct answer.

The idea is the same as generating rand7 using rand5. Assume rand5 generates a random number between 1 and 5, and rand7 is required to generate a number between 1 and 7. The code is as following


while(true) {
    int r = 5*(rand5 - 1) + rand5; // uniformly generate number between 1 to 25
    if (r <= 21) 
        return r % 7 + 1; // if r falls in between 1 ~ 20, module 7 to get a number between 0 ~ 6. the distribution is also uniform.
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s