rand() implementation

Hi,

I have read in several places ("Numerical Recipes", Knuth's books, etc.) the rand() facility is not a very good random number generator, because it is often poorly implemented. So I am planning to write my own implementation, but before that I would like to see the "native" rand() implementation on my computer (I have a Mac Intel with os 10.5 and I use gcc), how do I do that?

I looked in /usr/include/stdlib.h, but it just declares it:
int rand(void);
K&R show the following standard implementation:

unsigned long int next = 1;
/* rand: return pseudo-random integer on 0..32767 */
int rand(void)
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
/* srand: set seed for rand() */
void srand(unsigned int seed)
{
next = seed;
}

But implementations can vary from that. How can I check whether I am using that one when calling rand(). There should be a file (compiled or not) with the implementation, no? Where is it and how can I read it if it is compiled?

Cheers

In the original post you made, you claimed that you couldn't find the GNU C library source code. I can't imagine how that's possible though.

http://letmegooglethatforyou.com/?q=...ry+source+code

The very first link directs you right to the Savannah CVS repositories / download site.

To know exactly how rand() works for your particular C implementation, you need the source code for the C library that you're linking to. I can't even imagine why you would need this though, if you're writing your own rand() function that is.

Quote:

---

Originally Posted by habert79

I have read in several places ("Numerical Recipes", Knuth's books, etc.) the rand() facility is not a very good random number generator, because it is often poorly implemented.

---

That's the problem right there. Being half-informed can be worse than not being informed at all. Tons of people read an article somewhere about how rand() isn't perfect and wont do for certain statistical programs and decide that it is absolutely useless for almost everything.
The bottom line is that for almost all uses out there it is good enough.
Unless in your program you can show a difference between it and something else, or if you need an identical implementation between platforms, just use rand().

This is a fairly common question. And the answer is that you need to understand what sort of "quality" of random numbers you need for your particular application.

rand() is adequate for most things, as iMalc points out. It is not perfect, and the quality of the implementation varies from C library to C library. We had a case recently where someone wanted to call rand() multiple times to get a "50/50" distribution. Calling the standard rand() function 20 times to get a "a or b" answer is actually about 5-10% WORSE than calling it once. So it's not THAT easy to improve on it.

There are a few reasons you may want to replace it:
1. You need "better" (e.g. larger [RANDMAX is too small] or more sophisticated statistical distribution or some such). You may need to write some code to find out what the statistical properties of rand() is, and comparet that with your expected behaviour (e.g. distribution, mean/mode/standard deviation, likelyhood of low following high or high following low, chance of the same value twice in a row, etc, etc.
2. You need consistency: You want to have portable code that behaves the same way all the time, or you want to compare your results between different variants of code.
3. You need a non-linear distribution (e.g. "standard/normal distribution").
4. There is real money at stake, and you want to make sure no-one can "guess" how it's going to pan out - for example online poker games or some such, where someone could with REAL money.

If none of the criteria above (or any other criteria that you can think of) applies, then use rand() because it's already there.

--
Mats

Actually point 4 is an important one I had forgotten about.
There are algorithms out there that can predict the seed value given a sequence of random numbers generated by a LCG generator. Then they can predict all future output values.
In fact this issue is the one behind the massive DNS vulnerability that came to light recently, that is still far from having a solution deployed.

Yes you may also find some rand() implementatios that are poorly implemented. For the most part though, I'd say modern ones have a reasonable LCG in them. Certainly the most common ones do.

I guess it just comes down to: What do you actually want to use rand() for?