Mapping outcomes of binary number generator to decimal range $[1, x] $with equal probabilities

Question

I am looking for a function that maps each possible binary outcome from a binary number generator to a decimal range $[1, x]$ such that each value in the range has an equal chance of appearing.

For example, if we are given the range $[1, 64]$, then the mapping is easy. One function that can satisfy this is $f(b) = b_0\times2^0+b_1\times2^1+b_2\times2^2+b_3\times2^3+b_4\times2^4+b_5\times2^5$ + 1, where $b$ is an arbitrary binary number of five digits $(b_0b_1b_2b_3b_4b_5)_2$

However, if we are given the range $[1, 69]$, this mapping function does not work, since the numbers after $64$ would have no corresponding binary input. If we extended the length of binary digits to $6$ instead of $5$, the full range would have $128$ numbers but that is not evenly divisible by $69$ which means not all numbers in the $[1, 69]$ range get an equal chance to appear if we used such function to map from the binary number generator.

Any ideas/tricks on how to design an appropriate mapping function? It does not have to be linear. The only necessary condition is that each number in the given range should still have an equal chance after applying the mapping function.

Answer 1

If you want every binary random number to produce a unique decimal digit in 1..n then it’s only possible if n = 2^p with integer p.

Consider something simpler. R() produces random values in 0..7 i.e. 3-bit binary output. You want 0, 1, or 2 returned with equal probability. A simple rejection method works:

while (1) {
  n = R();
  if (n<6) return n/3; //or return n%3
{

For R() returning 0,1,2,3,4,5,6,7 The division method returns 0,0,1,1,2,2,x,x The remainder method returns 0,1,2,0,1,2,x,x

With a 32-bit machine take random32()*3 into a pair of 32-bit registers. The high-order register is almost uniform in 0..2.

If the random process is computationally expensive there are better-than-rejection methods.

For a taste of a better method consider random32() producing a binary fraction with the binary point to the left. Multiply by the range. Integer part is often random in 0..range-1. To check, ask if an infinite stream of 1 bits had been appended to the original binary fraction would the result have been higher. (hint: does the low-order register + range make a carry out? And yes, I like assembly language.) If not, you are done. Else use another random32() and you get to do the work of finishing he algorithm.