random number generator

[paskari]

does anyone know a random number generator in C which bounds the return value between upper and lower, and ensures a unique return value each time
I basically want to randomly assign numbers from 1 to n but I never want to aply the same number twice.

Thanks

[exterminator]

Read these FAQs - this and this. Hope these help!

[paskari]

yah those helped a bit, and I included the srand() as well, my problem is that I want to restrict the range instead of 0...RAND_MAX to 1....n
one way to do this is to make a variable mask, set mask to be:

mask=2^ceil(log(n)/log(2))  - 1;

so it is of the form 0*1*

then bitwise AND it with the return value of rand()

x = mask & rand();

that way, at least most of the time x would be less than x (since we took the ceiling some would be slightly bigger than x).

now here is the problem, I can include the math.h file, but I can't use the log() or ceil() functions, so I don't know what to do. I have included my code so you can take a look at it

//July 15, 2005
//Anna + Peyman Askari

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h> //for rand()
#include <math.h> //for logs and ceiling

//the threads begins in this function
void *runner(void *param); //the thread

int get_thread_number(){
	//aplies an algorithm to the thread ID to return the current thread number
	//subtracts it's thread ID by 2 to deal with the offset
	//turns it into an even number via multiplication and division by 2
	//divides it by 1024 since that is the average incrememnt every time
	return (((pthread_self()-2) /2)*2)/1024;
}


int get_thread_factor(int n){
	//randomly returns an integer between 1...n
	int x;//return value of rand()
	int mask;//we AND this mask with the value returned by rand()
	
	srand(time(NULL));
	//now we have to set the mask, it will be 2^ceil(log(n)/log(2))-1
	//This will ensure that the mask is some number of zeros followed by all 1's
	mask = 2^(ceil(log(n)/log(2))) - 1;
	//set x=n so it enters the loop
	x=n;
	while(x>=n){
		//iterate until we find a suitable x
		x = mask & rand();
	}
	//no we have to increment it by 1 since we currently have anumber
	//between 0...n-1 and we want 1...n
	x++;
	//printf("%d\n",x);
        return x;

}


int incr = 1024;

int main(int argc, char *argv[]){
	int i; //used in the for loop
	int ret; //the return value of any called function
	pthread_t tid; //thread identifier
	pthread_attr_t attr; //set of thread attributes
	
	if(argc != 3){
		//invalid number of arguements
		perror("Need at least 2 arguements\n");
		return -1;
	}
	if(1){
	  	//make sure both arguements are integers	  
	}
	if(atoi(argv[1])<0 || atoi(argv[2])<0){
	  	//negative arguements
		perror("Need positive integers as input\n");
		return -1;
	}
	
	//the below print statement just checks to see if get_thread_factor works
	get_thread_factor(atoi(argv[2]));
	
	for(i=0;i< atoi(argv[1]);i++){
		//get the default attributes
		pthread_attr_init(&attr);
		//create the thread
		//printf("%d",i+1);
		ret = pthread_create(&tid,&attr,runner,argv[1]);
		if(ret!=0){
		    //there was an error with the thread creation
		    perror("Threading error\n");
		    exit(-1);
		}
		//wait for thread to exit
		pthread_join(tid,NULL);
	}
	//the following print statement is for debugging purposes only
	printf("Control returned back to the calling process\n");
	return 0;
}

void *runner(void *param){
	
	//the below print statement shows that the output is always incremented by 10204
	//printf("-->%d --> %d = %d\n",pthread_self()-2,((pthread_self()-2) /2)*2,incr);
	
	//the following print statements tries to find a relationship amongst line number and thread ID
	//printf("-->%d --> %d = %d\n",pthread_self()-2,((pthread_self()-2) /2)*2,(((pthread_self()-2) /2)*2)/1024);
	//incr += 1024;
	
	//the bellow print statements makes sure get_thread_number works as expected
	//printf("=%d\n",get_thread_number());
	
	pthread_exit(0);
}

and now cc complains that it doesn't know what the log() and ceil functions are. What's going on? How can it include math.h, without generating compile time errors, but then when I try to use a function from math.h, it complains?

[golanshahar]

let me take a little guess here, you working on VC7.
and you calling log and ceil with (int) value (like i saw in your code)

VC7 doesnt have math functions that recieve int that is why you getting the compilation error cast the paramter to float or double and try again

mask = 2^(ceil(log((float)n)/log(2.0f))) - 1;

and do it the same on any spot you calling math fuctions. this is my guess.

if i helped dont forget to rate :-)
Cheers

[exterminator]

mask = 2^(ceil(log(n)/log(2))) - 1;

I am not sure what problem you are running into but I got the ceil() and log() running nicely without atleast compile errors. However, at the location quoted above try using the pow() function of the math library since it gave me a type-related error on VC++ 6.0. Hope this helps.

[KevinHall]

does anyone know a random number generator in C which bounds the return value between upper and lower, and ensures a unique return value each time
I basically want to randomly assign numbers from 1 to n but I never want to aply the same number twice.

Thanks

You can't simply use rand() for this. It's possible for rand() to return the same number twice. Even the code you posted in your second post can return a given number twice. What you need is an array of possible values. Let's say you have an array of n elements:

[e0, e1, e2, ... , e(n-2), e(n-1)]

Initial values will be (1+ the element indices):

[1,2,3,..., n-1, n]

Then you choose a random number between 0 and (n-1). Suppose you get

2. Then you will return 3 (because element 2 holds the value 3). But you need to make sure you don't use that number again. So what you do is copy the last element to element 2. Now you have:

[1,2,n,...,n-1, n]

The last element is in red because you don't need it anymore and can effectively treat it as no longer part of your array. For your next number, you choose a random number between 0 and (n-2). Even if the random generator returns 2 again, you'll have a unique number to return.

Anyway, I hope you get the idea. I'll leave the coding as an exercise for the reader.

- Kevin

P.S. log() and ceil() are expensive functions. It's usually sufficient to do the following (especially if you are using rand(), which if you read the FAQs is usually a poor random number generator anyway):

/* return a random integer between 1 and N */
int ranged_rand(int N)
{
    return 1+(int)((rand()*1.0/RAND_MAX)*N);
}

[Yves M]

Nice idea, Kevin. The only small thing is that you should exchange the last element with the element you've chosen, otherwise, if you copy it, you might choose the same number again.

[KevinHall]

Actually, copying is OK for per-sample generation. Because you don't include the last element in your choice for the next random number -- i.e. the effective shrinking of the array. Each trial leaves you with one less choice and so it is OK to leave junk (old values) at the end.

Now if we wanted to do a shuffle and generate a sequence ahead of time (as opposed to per-sample sequence generation), then swapping would be necessary.

- Kevin

[Yves M]

Good point. I read the OP's request as a random shuffle which it doesn't seem to be.

[paskari]

sorry for not posting in a while....I need sleep so badly

ok so here's where I'm at, I'm idiot, cuz I tried to complicate things, that whole mask idea I had:

mask=2^ceil(log(n)/log(2))  - 1;
x = rand() & mask;

it's just simply

x = rand() % n

more or less any way

I eventually did what I was trying to avoid doing...reinvent the wheel. I just stored an array of numbers already assigned and everytime I called rand, I checked to see if i had already called it. Obviously this is extrememly slow, but I can't think of any other ways.

I have another idea, and if i have time I'll try it, lets say I want numbers between 0 and 10. I call

x = rand() % 10

and lets say x is set to 3, and assign it (to whatever I originally wanted to)
next time I'll call

y = rand() % 2
z = (rand() % 7) + 4

it seems a little faster seeing as how if I have an array of size 1000 to randomly assign, my current algorithm takes forever. I guess I have to use recursion to implement this idea...this is where LISP would come in handy, just mapcar the puppy

oh and exterminator, I tried that srand(time(NULL)) approach, but it ended up giving me the same number everytime, and when I removed it, things worked fine.

[thre3dee]

ok heres how i generate a uniquely random number array
I have these two functions

int int_arrayfind (int * src, int value, int maxSize)
{
	for (int i = 0; i < maxSize; i++) if (src[i] == value) return i;
	return -1;
}

void int_fillrand (int * intArray, int lowestNum, int nArraySize)
{
	if (!intArray) return;
	srand ((unsigned int) time (0));
	int i = 0;
	for (; ++i < nArraySize;) intArray[i] = -1;
	i = 0;
	do {
		int rn = (rand () % nArraySize) + lowestNum;
		if ((arrayfind (intArray, rn, nArraySize)) == -1) {
			intArray[i] = rn;
			i++;
		}
	} while (i < nArraySize);
}

and an example

int list[20];
int_fillrand (list, 1, 20);

[wildfrog]

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

static int s_iLast = INT_MIN;
int random(int iMin, int iMax)
{
    int r;
    do {
        r = rand() % (iMax - iMin + 1) + iMin;
    } while (r == s_iLast);

    s_iLast = r;
    return r;
}

int _tmain(int argc, _TCHAR* argv[])
{
    srand(time(0));
    for (int i = 0; i < 20; i++)
        std::cout << random(0, 5) << std::endl;
    return 0;
}

- petter

[thre3dee]

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

static int s_iLast = INT_MIN;
int random(int iMin, int iMax)
{
    int r;
    do {
        r = rand() % (iMax - iMin + 1) + iMin;
    } while (r == s_iLast);

    s_iLast = r;
    return r;
}

int _tmain(int argc, _TCHAR* argv[])
{
    srand(time(0));
    for (int i = 0; i < 20; i++)
        std::cout << random(0, 5) << std::endl;
    return 0;
}

- petter

that would only check the last genrated number not all the numbers previously generated.

[wildfrog]

that would only check the last genrated number not all the numbers previously generated.

Well, I know that... and reading the original post once more... my bad.

- petter

[NMTop40]

Well this is C so we have to use a struct:

typedef struct RandomGen_tag
{
   unsigned int maxNum;
   unsigned int current;
   unsigned int numberCache[1]; /* trick often used in C */
} RandomGen;

RandomGen * CreateRandomGen( unsigned int maxNum )
{
   RandomGen* pRandomGen = (RandomGen *) malloc( sizeof( RandomGen ) + 
        (sizeof( maxNum ) - 1 )* sizeof( unsigned int ) );
   
  if ( pRandomGen ) /* this is C remember, malloc returns NULL when it fails */
  {
        unsigned int i;
        pRandomGen->maxNum = maxNum;
        pRandomGen->current = 0;
        for ( i=0; i< maxNum; ++i )
        {
            pRandomGen->numberCache[i] = i;
        }
   }
}

void DestroyRandomGen( RandomGen * pRandomGen )
{
   free( pRandomGen );
}

unsigned int GenRand( RandomGen * pRandomGen )
{
   unsigned int current = pRandomGen-.current;
   unsigned int i, valueCur;

   if ( current == pRandomGen->maxNum ) /* full */
   {
         return 0; /* indicate an error */
   }
   i = rand() % (pRandomGen->maxNum - pRandomGen->current);
   /* swap pRandomGen->numberCache[current] 
           and pRandomGen->numberCache[current+i] */
   valueCur = pRandomGen->numberCache[current + i];
   pRandomGen->numberCache[current+i] = pRandomGen->numberCache[current];
   pRandomGen->numberCache[current] = valueCur;
   ++pRandomGen->current;
   return valueCur+1;
}