How to generate a random number from whole range o

Question

unsigned const number = minimum + (rand() % (maximum - minimum + 1))

I know how to (easily) generate a random number within a range such as from 0 to 100. But what about a random number from the full range of int (assume sizeof(int) == 4), that is from INT_MIN to INT_MAX, both inclusive?

I don't need this for cryptography or the like, but a approximately uniform distribution would be nice, and I need a lot of those numbers.

The approach I'm currently using is to generate 4 random numbers in the range from 0 to 255 (inclusive) and do some messy casting and bit manipulations. I wonder whether there's a better way.

Answer 1

We should be able to do something that works no matter what the range of rand() or what size result we're looking for just by accumulating enough bits to fill a given type:

// can be any unsigned type.
typedef uint32_t uint_type;
#define RAND_UINT_MAX ((uint_type) -1)

uint_type rand_uint(void)
{
    // these are all constant and factor is likely a power of two.
    // therefore, the compiler has enough information to unroll
    // the loop and can use an immediate form shl in-place of mul.
    uint_type factor = (uint_type) RAND_MAX + 1;
    uint_type factor_to_k = 1;
    uint_type cutoff = factor ? RAND_UINT_MAX / factor : 0;
    uint_type result = 0;

    while ( 1 ) {
        result += rand() * factor_to_k;
        if (factor_to_k <= cutoff)
            factor_to_k *= factor;
        else
            return result;
    }
}

Note: Makes the minimum number of calls to rand() necessary to populate all bits.

Let's verify this gives a uniform distribution.

At this point we could just cast the result of rand_uint() to type int and be done, but it's more useful to get output in a specified range. The problem is: How do we reach INT_MAX when the operands are of type int?

Well... We can't. We'll need to use a type with greater range:

int uniform_int_distribution(int min, int max)
{
    // [0,1) -> [min,max]
    double canonical = rand_uint() / (RAND_UINT_MAX + 1.0);
    return floor(canonical * (1.0 + max - min) + min);
}

As a final note, it may be worthwhile to implement the random function in terms of type double instead, i.e., accumulate enough bits for DBL_MANT_DIG and return a result in the range [0,1). In fact this is what std::generate_canonical does.

Answer 2

On my system RAND_MAX is 32767 which is 15 bits. So for a 32-bit unsigned just call three times and shift, or, mask etc.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void){
    unsigned rando, i;
    srand((unsigned)time(NULL));
    for (i = 0; i < 3; i++) {
        rando = ((unsigned)rand() << 17) | ((unsigned)rand() << 2) | ((unsigned)rand() & 3);
        printf("%u\n", rando);
    }
    return 0;
}

Program output:

3294784390
3748022412
4088204778

Answer 3

For reference I'm adding what I've been using:

int random_int(void) {
  assert(sizeof(unsigned int) == sizeof(int));
  unsigned int accum = 0;
  size_t i = 0;
  for (; i < sizeof(int); ++i) {
    i <<= 8;
    i |= rand() & 0x100;
  }
  // Attention: Implementation defined!
  return (int) accum;
}

But I like Weather Vane's solution better because it uses fewer rand() calls and thus makes more use of the (hopefully good) distribution generated by it.