Roy's musings

Some time back a friend asked me an algorithm question: Given an integer random number generator randomN() that can generate random number in the range [0, N), how will you generate random numbers in the range [0, M) where M I used modulo arithmetic to generate the desired random numbers in the range [0, M). And I reasoned out that if N = q*M + r, every number in the range [0, r] has an occurrence probability of (q+1)/N, but the numbers in the range [r+1, M) has an occurrence probability of only q/N. It is easy to visualize this. See the diagram below: You can see that we can divide line of length N units (given in green) by lines of length M units (given in black). When N is not exactly divisible by M, in the last part alone we have only r units. So if we choose a random integer in the line represented in green, and then take a modulo M on the value, all the values except the values in the range [r+1, M) (represented in red) will occur q+1 times. But the values in that int...