How to generate a random integer number from within a range

Question

This is a follow on from a previously posted question   How to generate a random number in C   I wish to be able to generate a random number from within a particular range  such as 1 to 6 to mimic the sides of a die   How would I go about doing this

User · Answer

For those who understand the bias problem but can't stand the unpredictable run-time of rejection-based methods, this series produces a progressively less biased random integer in the [0, n-1] interval:

r = n / 2;
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
...

It does so by synthesising a high-precision fixed-point random number of i * log_2(RAND_MAX + 1) bits (where i is the number of iterations) and performing a long multiplication by n.

When the number of bits is sufficiently large compared to n, the bias becomes immeasurably small.

It does not matter if RAND_MAX + 1 is less than n (as in this question), or if it is not a power of two, but care must be taken to avoid integer overflow if RAND_MAX * n is large.

User · Answer

Following on from  Ryan Reich s answer  I thought I d offer my cleaned up version  The first bounds check isn t required given the second bounds check  and I ve made it iterative rather than recursive  It returns values in the range  min  max   where max  gt   min and 1 max-min  lt  RAND MAX   unsigned int rand interval unsigned int min  unsigned int max        int r      const unsigned int range   1   max - min      const unsigned int buckets   RAND MAX   range      const unsigned int limit   buckets   range          Create equal size buckets all in a row  then fire randomly towards        the buckets until you land in one of them  All buckets are equally        likely  If you land off the end of the line of buckets  try again         do               r   rand          while  r  gt   limit        return min    r   buckets

User · Answer

While Ryan is correct  the solution can be much simpler based on what is known about the source of the randomness  To re-state the problem     There is a source of randomness  outputting integer numbers in range  0  MAX  with uniform distribution   The goal is to produce uniformly distributed random integer numbers in range  rmin  rmax  where 0  lt   rmin  lt  rmax  lt  MAX    In my experience  if the number of bins  or  boxes   is significantly smaller than the range of the original numbers  and the original source is cryptographically strong - there is no need to go through all that rigamarole  and simple modulo division would suffice  like output   rnd next      rmax 1   if rmin    0   and produce random numbers that are distributed uniformly  enough   and without any loss of speed  The key factor is the randomness source  i e   kids  don t try this at home with rand      Here s an example proof of how it works in practice  I wanted to generate random numbers from 1 to 22  having a cryptographically strong source that produced random bytes  based on Intel RDRAND   The results are    Rnd distribution test  22 boxes  numbers of entries in each box         1  409443    4 55   2  408736    4 54   3  408557    4 54   4  409125    4 55   5  408812    4 54   6  409418    4 55   7  408365    4 54   8  407992    4 53   9  409262    4 55  10  408112    4 53  11  409995    4 56  12  409810    4 55  13  409638    4 55  14  408905    4 54  15  408484    4 54  16  408211    4 54  17  409773    4 55  18  409597    4 55  19  409727    4 55  20  409062    4 55  21  409634    4 55  22  409342    4 55     total  100 00     This is as close to uniform as I need for my purpose  fair dice throw  generating cryptographically strong codebooks for WWII cipher machines such as http   users telenet be d rijmenants en kl-7sim htm  etc   The output does not show any appreciable bias   Here s the source of cryptographically strong  true  random number generator  Intel Digital Random Number Generator and a sample code that produces 64-bit  unsigned  random numbers   int rdrand64 step unsigned long long int  therand      unsigned long long int foo    int cf error status     asm  rdrand   rax            mov  1   edx            cmovae   rax   rdx            mov   edx  1            mov   rax   0     r  foo    r  cf error status     rax    rdx             therand   foo    return cf error status      I compiled it on Mac OS X with clang-6 0 1  straight   and with gcc-4 8 3 using  -Wa q  flag  because GAS does not support these new instructions

User · Answer

Here is a slight simpler algorithm than Ryan Reich s solution       Begin and end are  inclusive     gt   begin  end  uint32 t getRandInterval uint32 t begin  uint32 t end        uint32 t range    end - begin    1      uint32 t limit     uint64 t RAND MAX   1  -    uint64 t RAND MAX   1    range           Imagine range-sized buckets all in a row  then fire randomly towards        the buckets until you land in one of them  All buckets are equally        likely  If you land off the end of the line of buckets  try again         uint32 t randVal   rand        while  randVal  gt   limit  randVal   rand             Return the position you hit in the bucket   begin as random number     return  randVal   range    begin        Example  RAND MAX    16  begin    2  end    7        gt  range    6   1   end - begin        gt  limit    12  RAND MAX   1  -   RAND MAX   1    range   The limit is always a multiple of the range  so we can split it into range-sized buckets      Possible-rand-output  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16     Buckets               0  1  2  3  4  5  0  1  2  3  4  5  X  X  X  X  X      Buckets   begin       2  3  4  5  6  7  2  3  4  5  6  7  X  X  X  X  X   1st call to rand     gt  13       13 is not in the bucket-range anymore   gt   limit   while-condition is true           retry    2nd call to rand     gt  7       7 is in the bucket-range   lt  limit   while-condition is false           Get the corresponding bucket-value 1  randVal   range  and add begin       gt  3

User · Answer

All the answers so far are mathematically wrong   Returning rand     N does not uniformly give a number in the range  0  N  unless N divides the length of the interval into which rand   returns  i e  is a power of 2    Furthermore  one has no idea whether the moduli of rand   are independent  it s possible that they go 0  1  2       which is uniform but not very random   The only assumption it seems reasonable to make is that rand   puts out a Poisson distribution  any two nonoverlapping subintervals of the same size are equally likely and independent   For a finite set of values  this implies a uniform distribution and also ensures that the values of rand   are nicely scattered   This means that the only correct way of changing the range of rand   is to divide it into boxes  for example  if RAND MAX    11 and you want a range of 1  6  you should assign  0 1  to 1   2 3  to 2  and so on   These are disjoint  equally-sized intervals and thus are uniformly and independently distributed   The suggestion to use floating-point division is mathematically plausible but suffers from rounding issues in principle   Perhaps double is high-enough precision to make it work  perhaps not   I don t know and I don t want to have to figure it out  in any case  the answer is system-dependent   The correct way is to use integer arithmetic   That is  you want something like the following    include  lt stdlib h gt     For random    RAND MAX     Assumes 0  lt   max  lt   RAND MAX    Returns in the closed interval  0  max  long random at most long max      unsigned long        max  lt   RAND MAX  lt  ULONG MAX  so this is okay      num bins    unsigned long  max   1      num rand    unsigned long  RAND MAX   1      bin size   num rand   num bins      defect     num rand   num bins     long x    do      x   random             This is carefully written not to overflow   while  num rand - defect  lt    unsigned long x         Truncated division is intentional   return x bin size      The loop is necessary to get a perfectly uniform distribution   For example  if you are given random numbers from 0 to 2 and you want only ones from 0 to 1  you just keep pulling until you don t get a 2  it s not hard to check that this gives 0 or 1 with equal probability   This method is also described in the link that nos gave in their answer  though coded differently   I m using random   rather than rand   as it has a better distribution  as noted by the man page for rand      If you want to get random values outside the default range  0  RAND MAX   then you have to do something tricky   Perhaps the most expedient is to define a function random extended   that pulls n bits  using random at most    and returns in  0  2  n   and then apply random at most   with random extended   in place of random    and 2  n - 1 in place of RAND MAX  to pull a random value less than 2  n  assuming you have a numerical type that can hold such a value   Finally  of course  you can get values in  min  max  using min   random at most max - min   including negative values

User · Answer

In order to avoid the modulo bias  suggested in other answers  you can always use   arc4random uniform MAX-MIN  MIN   Where  MAX  is the upper bound and  MIN  is lower bound  For example  for numbers between 10 and 20   arc4random uniform 20-10  10  arc4random uniform 10  10   Simple solution and better than using  rand     N

User · Answer

Here is a formula if you know the max and min values of a range  and you want to generate numbers inclusive in between the range   r    rand      max   1 - min     min

User · Answer

As said before modulo isn t sufficient because it skews the distribution  Heres my code which masks off bits and uses them to ensure the distribution isn t skewed   static uint32 t randomInRange uint32 t a uint32 t b        uint32 t v      uint32 t range      uint32 t upper      uint32 t lower      uint32 t mask       if a    b            return a             if a  gt  b            upper   a          lower   b        else           upper   b          lower   a              range   upper - lower       mask   0        XXX calculate range with log and mask  nah  too lazy         while 1            if mask  gt   range                break                    mask    mask  lt  lt  1    1              while 1            v   rand    amp  mask          if v  lt   range                return lower   v                       The following simple code lets you look at the distribution   int main          unsigned long long int i        unsigned int n   10      unsigned int numbers n         for  i   0  i  lt  n  i              numbers i    0             for  i   0   i  lt  10000000   i             uint32 t rand   random in range 0 n - 1           if rand  gt   n               printf  bug  rand out of range  u n   unsigned int rand               return 1                    numbers rand     1             for i   0  i  lt  n  i              printf   u   u n  i numbers i

User · Answer

Will return a floating point number in the range  0 1     define rand01      double random      double  RAND MAX

User · Answer

Wouldn t you just do   srand time NULL    int r     rand     6     1      is the modulus operator  Essentially it will just divide by 6 and return the remainder    from 0 - 5

User · Answer

unsigned int randr unsigned int min  unsigned int max           double scaled    double rand   RAND MAX          return  max - min  1  scaled   min      See here for other options

[c] How to generate a random integer number from within a range

Examples related to c

Examples related to random