Generate randN given rand1 | Hello World
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.
Read full article from Generate randN given rand1 | Hello World
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.
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.}