Maintain Uniform Distribution across Subranges

Question

Note: this is a continuation of Generate Random Number outside Bounds.

I have a function (thanks to the previous question) with the following prototype which returns an integer in the range $[0,b]$, $b \le UINT\_MAX$:

unsigned int randrange(unsigned int b)

Now I want to create a function which returns an integer in the range $[a,b]$, $a \ge INT\_MIN$, $b \le INT\_MAX$, $a \le b$:

int randint(int a, int b)

I can't apply the techniques from the previous question and also create cross-platform compatible C code. Specifications from the standard:

• an unsigned integer may not necessarily hold a value larger than signed integer (due to padding bits)

  $INT\_MAX \le UINT\_MAX$

• $\lvert INT \_MIN \rvert$ may exceed UINT_MAX (two's complement)

  $\lvert INT\_MAX \rvert - 1 \le UINT\_MAX$

• the range of a signed integer may exceed the range of an unsigned integer (follows from the previous two)

  $INT\_MAX - INT\_MIN \le 2 * UINT\_MAX + 1$

• int is the widest type guaranteed by the standard

  $char \le short \le int \le long \le long\ long$

• the ranges $[INT\_MIN,-1]$, $[0,INT\_MAX]$ are not guaranteed to be of same length, though they will always be centered around zero

  • the ranges for one's complement and sign/magitude are: $[-x,x]$
  • the ranges for two's complement are: $[-(x+1),x]$

Also:

• signed integers may implement the following encodings:

  • two's complement
  • one's complement
  • sign/magnitude

• converting an unsigned integer to a signed integer is implementation-defined behaviour if the value of the unsigned integer cannot be represented by the signed integer.

So, I have two possible approaches:

1. Use the alternative solution from the linked question: Generate a particular set of digits/bits rather than to a maximum value.

   First generate n bits of random information, where n is the number of value bits in a signed integer:

   (signed int)randrange(INT_MAX);
   

   Generate the sign bit: 0 if positive, 1 if negative. The sign bit must be applied differently depending on the signed integer encoding.

   randrange(1);
   

   Sign/magnitude has uniform distribution, and therefore is simple to work with:

   if (randrange(1))
     randombits = -randombits
   

   One's complement has an extra zero, which should be excluded as it doesn't affect the final range:

   if (randrange(1)) {
     // avoid generating negative zero
     do {
       randombits = (signed int)randrange(INT_MAX);
     while (r == INT_MAX);
     randombits = -randombits
   

   Two's complement has an extra negative number, which is independent of the even odds of a negative number:

   // each number is unique. the odds of a single number appearing in any
   // range, be it [INT_MIN+1,INT_MAX] or [INT_MIN,INT_MAX], are identical
   // (within the range)
   // so compare against any number
   if randombits == 0 {
     if (randrange(1) {
       randombits = INT_MIN;
     }
   } else {
     // otherwise, even odds for negative
     randombits = -randombits
   }
   

   Then apply the usual rejection sampling if $randombits > b$ or $randombits < a$, with range-scaling optimizations as described in the original question.

   This approach almost seems to good to be true...

2. Use a numerical method

   Detect when randint's range exceeds the maximum range of randrange:

   // outside the bounds of randrange
   if (b >= 0 && a < 0 && a + INT_MAX > b) {
     // following code goes inside this conditional
   }
   

   Split the range while maintaining uniform distribution. The probability of generating a random number within the bounds of the smaller range is assumed to reflect the size (and probability) ratio of both ranges as follows.

   These are my assumptions:

   Given two subranges of Z, X and Y, such that $length(X) + length(Y) = length(Z)$, the chance of a random number z from Z appearing in either X or Z is: $$P(z\ in\ X) = length(X)/length(Z)$$ $$P(z\ in\ Y) = length(Y)/length(Z)$$

   If the distribution of z in Z is uniform, then to maintain a uniform distribution in both X and Y, only the relative probabilities need to be known: $$P(X\ vs\ Y) = length(X)/length(Y)$$ $$P(Y\ vs\ X) = length(Y)/length(Z)$$

   This is good, because length(Z) is incalculable.

   However, instead of calculating a ratio, it can be simulated by a random number r: $$P(X\ vs\ Y) = \begin{cases}P(r \ge length(Y)), r = randrange(length(X)) & length(X) \ge length(Y) \\ P(r \le length(Y)), r = randrange(length(Y)) & \text{otherwise} \end{cases}$$

   Assuming all that is true, then:

   // Consider (INT_MIN,-1) and (0,INT_MAX)
   // Swap to negative before comparing to avoid overflow
   if (-b > a + 1) {
     // the positive range is greater
     if (-randrange(0,b) < a + 1)
       return randrange(0,b);
     else
       return -randrange(1,-a);
   } else if (-b < a + 1) {
     // the negative range is greater
     if (randrange(0,-(a+1)) > b)
       return -randrange(0,-(a+1)) + a;
     else
       return randrange(0,b);
   } else {
     // the ranges are of equal length
     if (randrange(1))
       return randrange(0,b);
     else
       return randrange(0,b) + a;
   }
   

   This approach also seems to good to be true.

My question: are these approaches valid?

Answer 1

If you have access to floating point numbers, why not generate a $[0, 1)$ random number U and then compute $R = \lfloor a + U (b-a+1)\rfloor$?

Answer 2

The general problem with all complicated approaches one can come up (e.g., randomly choosing bits, or rounding floating point number, etc) is to prove that the resulting set of random numbers are really equally distributed.

However, in your case, things would appear to be relatively simple. To draw a number $x \in [A,B)$, draw a random number $y\in [0,B-A)$ and compute $x=y+A$. If $y$ is equally distributed, then so is $x$.

In your case, you know that $[A,B)$ is an interval in the signed integers (of the C programming language). Consequently, $[0,B-A)$ is an interval in the unsigned integers for which the question you linked to already has an algorithm.