This is a programming challenge I proposed to my development team today, and we had fun with it, so I thought I'd present it to you.
The challenge is to create a random number generation function, similar to rand() which will have a higher probability of returning low numbers than high numbers. The declaration for the function is
int nuRand(const int nUpper)
where nUpper is the upper boundary of the random numbers the function should return (non-inclusive) So calling "nuRand(100)" will return random numbers of the range 0 to 99.
The rules:
- The function is to be written in C/C++ (no assembly)
- The code must be 100% yours.. no 3rd party libraries Edit: You may use the STL and CRT, so rand() and abs() are fine
- The probability curve of the returned values may be anything you wish, it may even be linear, just so long as there is a much higher probability of getting a '0' returned than a '99'.
edit: I'd like to see a nice linear distribution though [smile]
- Bonus points awarded for speed and memory usage.
- new: I don't have a linux box, so please make sure your functions will compile under MSVC6
- new: Please no anonymous posting! I will run your functions, but you won't get the leadership.
- new: Please place lengthy code exerpts in [ source ] [/ source] brackets. See the faq for more info.
If you post your functions here, I will test them when I get home from work, and update this post with the current leader(s) in the categories of execution speed and memory usage.
Good luck.
Results:
smart_idiot curently holds the speed record of 1196.1585ms in the speed test.
The function posted by Mr. "Anonymous Poster" was actually faster (979.9690), but anonymous posters can't get the credit, I'm afraid. The curve was also VERY steep.. out of 10000000 function calls, 9970000 returned '0'.
Wyrframe: 1484.7239ms (btw, your rand2() function will throw a div/0 error, so this is rand2_edited's time)
Zahlman: 2073.2392ms The distribution from your function was nice and linear.. I like :)
Conner McCloud, I wasn't able to actually get your function to return. It was getting stuck in an infinite loop somewhere.
I'm not going to bother with testing memory usage.. They're all so close... I was afraid someone would do something like:
int nuRand(const int nUpper)
{
int *aNumbers = new int[nUpper];
for(int n=nUpper; n > 0; n--)
{
aNumbers[n-1] = rand()%n;
}
int nRet = aNumbers[rand()%nUpper];
delete [] aNumbers;
return nRet;
}
My test function: A preliminary loop of 10,000,000 function calls is performed to test the output of the function, which I then graph in excel to see the curve. After that, I do a number of 1000000-call iterations with various powers of two for the speed test.
int main(int argc, char* argv[])
{
LARGE_INTEGER liFreq, liStart, liStop;
double dTicks;
QueryPerformanceFrequency(&liFreq);
int aCounts[100];
memset(aCounts, 0, sizeof(int)*100);
int nTemp, n;
for(n=0; n <10000000; n++)
{
nTemp = nuRand(100);
if(nTemp >= 100 || nTemp < 0)
{
printf("Function returned a random # outside of parameters! (%d)\r\n", nTemp);
break;
}
else
aCounts[nTemp]++;
}
for(n=0; n < 100; n++)
{
printf("%3d = %8d\r\n",n, aCounts[n]);
}
QueryPerformanceCounter(&liStart);
int max=0x40000000;
for(int i=1; i < max; i<<=1)
{
for(n=0; n < 1000000; n++)
{
nuRand(i);
}
}
QueryPerformanceCounter(&liStop);
dTicks = liStop.QuadPart-liStart.QuadPart;
printf("Elapsed = %6.4fms\r\n",(dTicks/liFreq.QuadPart)*1000);
printf("\r\nDone! Press [enter] to quit...");
getchar();
return 0;
}
[Edited by - pragma Fury on June 23, 2005 11:45:33 AM]