Random Integer Generator

[porterboy76]

Pieter Droogendijk wrote

Date: Mon, Aug 18 2003 2:17 pm
Groups: comp.lang.c

I usually use a function like this:
min+(int) ((double)((max+1)-min)*rand()/(RAND_MAX+1.0))
to get a random integer between min and max. I've seen
that it's 'random enough' for my taste. No performance
beast though...

There is a problem with this. A histogram will show a
non-uniform distribution of integers, if the range min:max
is a large proportion of RAND_MAX, or not a factor
of RAND_MAX. I use the following (by the way, I'm a newbie
C programmer; I think the algorithm is good even if the
code is not.)

/*
generate an array a of N random
integers drawn uniformly from the set
X = {x | amin <= x <= amax, x \in Z}
*/

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


void rand_int_array(int a[], size_t N, int amin, int amax)
{
// argument checking ------------------------
if (amin>=amax)
{
printf("Improper use of function randint");
exit(EXIT_FAILURE);
}

// initialise --------------------------------
int nsection, lsection, uplim, i;
double x;
nsection = 1+amax-amin;
lsection = RAND_MAX/nsection;
uplim = lsection*nsection;

// random number generator -------------------

// seed rand() still to do...

// fill array
for (i=0;i<N;i++)
{
do
{
x = rand();
}
while (x>=uplim);

a = amin+(int) (x/lsection);
}
}


Maybe someone could suggest a good way to
seed rand() I am still reading up about this.

 

[baja]

Do you need to generate random number only once
or you are generating them in a looop

i.e. do you want to generate N different numbers between min and max
or any one random number between min and max

Pieter Droogendijk wrote
Date: Mon, Aug 18 2003 2:17 pm
Groups: comp.lang.c

I usually use a function like this:
min+(int) ((double)((max+1)-min)*rand()/(RAND_MAX+1.0))
to get a random integer between min and max. I've seen
that it's 'random enough' for my taste. No performance
beast though...

There is a problem with this. A histogram will show a
non-uniform distribution of integers, if the range min:max
is a large proportion of RAND_MAX, or not a factor
of RAND_MAX. I use the following (by the way, I'm a newbie
C programmer; I think the algorithm is good even if the
code is not.)

/*
generate an array a of N random
integers drawn uniformly from the set
X = {x | amin <= x <= amax, x \in Z}
*/

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


void rand_int_array(int a[], size_t N, int amin, int amax)
{
// argument checking ------------------------
if (amin>=amax)
{
printf("Improper use of function randint");
exit(EXIT_FAILURE);
}

// initialise --------------------------------
int nsection, lsection, uplim, i;
double x;
nsection = 1+amax-amin;
lsection = RAND_MAX/nsection;
uplim = lsection*nsection;

// random number generator -------------------

// seed rand() still to do...

// fill array
for (i=0;i<N;i++)
{
do
{
x = rand();
}
while (x>=uplim);

a = amin+(int) (x/lsection);
}
}


Maybe someone could suggest a good way to
seed rand() I am still reading up about this.

 

[porterboy76]

N integers...
In my code I am generating an array
of random numbers.

 

[baja]

well the best way for me will be
take an array of N numbers
fill up each elemnt in increasing order from min to max
i.e.
if N = 4
min = 3 and max = 6
then array elements should be like
3,4,5,6

now in a loop

for(i = 0, j= N ; i <= N ; i++,j--){
number = rand()%j;
newNumber = array[number]; /* save it somewhere , or do with it
whatever you want to do ,
this is your new random number.
I am considering that I have to just print N random numbers*/
printf("%d",newNumber);
swap(array[j],array[number]);
}


If you had to do something different than either you will have to
modify above loop
or Your random numbers will be in revrese order in your array.

advantage is aboove code is that it will take exactly N random calls to
genrate N different numbers....
so no colloision

 

[donnacha.daly]

Repetitions are allowed, my only constraint is normal distribution.
AFAIK your code generates an array of unrepeating ints. Look at
it another way, set N = 1, and my code does the same task as the
code I snipped in the OP, generate a single random integer from
a specified range. However by doing...

do
{
x = rand();
}
while (x>=uplim);

a = amin+(int) (x/lsection);

I remove the bias.

 

[donnacha.daly]

eh, now I see that my code commenting was ambiguous...
and I see why you thought I was seeking N distinct integers...

 

[baja]

we can always modify that to meet requirements.....
if we do not want different integres and want only from 2 , 6, 8
we can fill array initially with 2,6,8
essence is array index will be generated randomly ......
contents you can fill the way you want them to be

with the previous 2003 )solution i m more worried due to
do{
x = rand();
}while (x>=uplim);

won't it increase unnecessary calls to rand()

 

[porterboy76]

It is true that the number of calls to rand() could be large
before returning a value in the desired range. In practise,
this tends not to be significant. For example, suppose
I want to pick an integer between 1 and 52, representing
a card from a deck. The above algorithm gives...

RAND_MAX = 2147483647
nsection = 52
lsection = 41297762
uplim = 2147483624

how many times will rand() return a value greater than uplim
but less than RAND_MAX, compared to the times it returns
a value less than uplim... not many! I acceed that it could be
a problem in other examples, where nsection is large (>1e5).

By the way, any other way to improve my code would be appreciated.
I know algorithms quite well, but my C knowledge is very limited.

 

[porterboy76]

Ah, I see it's been answered in the FAQ!
http://c-faq.com/lib/randrange.html