rand() implementation

This is a discussion on rand() implementation within the C Programming forums, part of the General Programming Boards category; Hi, I have read in several places ("Numerical Recipes", Knuth's books, etc.) the rand() facility is not a very good ...

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    1

    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

  2. #2
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    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.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by habert79 View Post
    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().
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21