1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $B - A$ cannot be calculated, as it might exceed the range of unsigned integers on some machines, per the specification. $\endgroup$ – user19087 Dec 29 '15 at 19:41
  • $\begingroup$ I plan on using Pearson's chi-squared test of goodness of fit to check for uniform distribution: chi-squared with too many degrees of freedom $\endgroup$ – user19087 Dec 29 '15 at 19:45
  • $\begingroup$ If $B$ and $A$ are signed integers, I cannot see how $B-A$ cannot be represented as an unsigned integer with the same number of bits. It may be that you have to compute the difference in long long int (or long long unsigned), for example, but the difference must fit into an unsigned int. $\endgroup$ – Wolfgang Bangerth Dec 29 '15 at 23:59
  • $\begingroup$ In some machines, UINT_MAX == ULONG_MAX == ULLONG_MAX. In some extremely uncommon machines, INT_MAX == UINT_MAX. $\endgroup$ – user19087 Dec 30 '15 at 0:04
  • $\begingroup$ Yes, if you happen to be on a system where UINT_MAX==ULONG_MAX==ULLONG_MAX, then you need to compute the difference differently, for example by computing $B-A$ as $B+(-A)$ if $A$ is negative, and casting both arguments to the addition to unsigned first. The second case, INT_MAX==UINT_MAX is a bigger problem, but I cannot imagine a system where that may be true. Can you point out one? $\endgroup$ – Wolfgang Bangerth Dec 30 '15 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.