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 (http://www.codeguru.com/forum/showthread.php?s=&threadid=284877) and this (http://www.codeguru.com/forum/showthread.php?s=&threadid=284875). Hope these help! :thumb:

[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. :blush:

- 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;
}

[RoboTact]

Read my posts and links in them in thread Shuffle algorithm (http://www.codeguru.com/forum/showthread.php?t=339310&page=1&pp=15)

Some bugs.
When you call srand() with identical parameters, you get identical random number sequences, so if you call srand(time(0)) every time you generate random sequence, you get the same result during the second. There generally is no point in calling srand() more then once.
You algorithms's average execution time is O(n^2).
Don't use rand()%n for large n.

int i = 0;
for (; ++i < nArraySize;) intArray[i] = -1;Note that it doesn't fill intArray[0]

int list[20];
int_fillrand (list, 1, 20);
Even in C it's better to use OOP. You would bump in all kinds of problems if system is complex enough.

[paskari]

hey do you guys know anyway to get a thread (say thread 3) and tell it to stop what it's doing and start a different thread?

like


restart(3,&attr,some_function());


I have n threads, i need n-1 of them to write to a globabl variable "buffer", and everytime one of them writes to buffer, thread n has to read buffer. How can I synchronize them?

[RoboTact]

Are you sure you posted the question in the right thread?
Draw the timeline. Mark points of starting and ending of different operations on resource. Note the dependancies between them. Point 1: resourse can't be accessed (for reading or writing) by more then one thread. So, enclose the access in mutex. Point 2: reading thread should wait for writing thread to make write access. Just wake it up within brackets of mutex at any time while writing.

[paskari]

Are you sure you posted the question in the right thread?
Draw the timeline. Mark points of starting and ending of different operations on resource. Note the dependancies between them. Point 1: resourse can't be accessed (for reading or writing) by more then one thread. So, enclose the access in mutex. Point 2: reading thread should wait for writing thread to make write access. Just wake it up within brackets of mutex at any time while writing.
ya you're right, I'll delete the last post I made and put it in a new thread