rand() questions

I'm working in a randomized algorithm. In a heavy loop, I'm using rand() function. To determine the complexity of the algorithm, I need to know the complexity of rand(). I'm assuming it runs in constant time, but I'm not sure. Is its running time constant?

Also, I need to know the period of the sequence generated by rand(). Is it or any upper bound known (except RAND_MAX, I think the upper bound is lower than RAND_MAX)? I would like to see the implementation of rand(). I could not find it in VS 2008's cstdlib file. Where can I find it?

Any help will be greatly appreciated. Thanks.
--
~Donotalo()

Comments

  • I have some code for it, but it can't share it because of copyright issues... :-( Google for "Lehmer random number generator" though.

    I can tell you this about the "Lehmer" implementation (which seems to be the most common one): Roughly it uses the seed from srand() and divide+modulo this with a constant, then multiplies the results with some other constants. I have no idea about the math theory of the algorithm myself, but programming-wise it is not a heavy task.

    The time it takes should be short and deterministic, ie pretty much constant runtime. What you need to be aware of is that rand() is a typical example of a non-thread safe function, since it typically accesses and alters the seed obtained from srand() through a global static variable. So be careful with it in a multi-thread application.
  • You can check my web site about some information about rand()

    http://cpp-knowledgestore.blogspot.com/
  • Thanks to both of you.

    To get the period of the sequence generated by Visual Studio 2005's rand() function, I ran the following program:
    [code]
    #include
    #include
    #include
    using namespace std;

    int main()
    {
    int i, seed, r, first;

    seed = time(0);

    srand(seed);
    first = rand();

    for (i = 0; i < 333333; i++) {
    r = rand();
    if (r == first)
    break;
    }

    cout << "RAND_MAX = " << RAND_MAX << endl
    << "seed = " << seed << endl
    << "first = " << first << endl
    << "period = " << i + 1 << endl << endl;

    return 0;
    }
    [/code]
    RAND_MAX is 32767. Surprisingly, I got period more than RAND_MAX for several seed values! How is that possible?
    --
    ~Donotalo()
  • : Thanks to both of you.
    :
    : To get the period of the sequence generated by Visual Studio 2005's
    : rand() function, I ran the following program:
    : [code]:
    : #include
    : #include
    : #include
    : using namespace std;
    :
    : int main()
    : {
    : int i, seed, r, first;
    :
    : seed = time(0);
    :
    : srand(seed);
    : first = rand();
    :
    : for (i = 0; i < 333333; i++) {
    : r = rand();
    : if (r == first)
    : break;
    : }
    :
    : cout << "RAND_MAX = " << RAND_MAX << endl
    : << "seed = " << seed << endl
    : << "first = " << first << endl
    : << "period = " << i + 1 << endl << endl;
    :
    : return 0;
    : }
    : [/code]:
    : RAND_MAX is 32767. Surprisingly, I got period more than RAND_MAX for
    : several seed values! How is that possible?
    : --
    : ~Donotalo()


    RAND_MAX is in this case equal to the maximal number that can be stored in a 16 bits signed integer (-32678 to 32767). 333333 > 32767 by a long shot, so you're dealing with plenty of overflow issues here. Make the counter variable a bigger variable, like perhaps an unsigned int32.
    Best Regards,
    Richard

    The way I see it... Well, it's all pretty blurry
  • RAND_MAX is the maximum value of the rand() [italic]range[/italic]. rand() will return a number between 0 and RAND_MAX. It has nothing to do with the randomness ("period") of the function.

    There are no overflow issues in the code, Visual Studio is a 32-bit compiler.
  • : RAND_MAX is the maximum value of the rand() [italic]range[/italic].
    : rand() will return a number between 0 and RAND_MAX. It has nothing
    : to do with the randomness ("period") of the function.
    :
    : There are no overflow issues in the code, Visual Studio is a 32-bit
    : compiler.

    Yeah you're right... wasn't thinking straight.
    But it's still impossible to get a period greater than RAND_MAX+1 (for a Linear Congruent Generator). So there is something not right ...
    Unless of course it's not using this method (I know for a fact VC++6 was)

    EDIT: I checked the VS2005 implementation, and it's indeed a bit different. It's sort of linear (but not entirely) ... so, yes, it is possible to get period >= RAND_MAX

    Best Regards,
    Richard

    The way I see it... Well, it's all pretty blurry
  • : EDIT: I checked the VS2005 implementation, and it's indeed a bit
    : different. It's sort of linear (but not entirely) ... so, yes, it is
    : possible to get period >= RAND_MAX
    :
    : Best Regards,
    : Richard
    :
    : The way I see it... Well, it's all pretty blurry

    I'm interested to see the implementation too. But couldn't find the definition of rand() function. Can you please tell where can I find the implementation of rand()?
    --
    ~Donotalo()
  • : : EDIT: I checked the VS2005 implementation, and it's indeed a bit
    : : different. It's sort of linear (but not entirely) ... so, yes, it is
    : : possible to get period >= RAND_MAX
    : :
    : : Best Regards,
    : : Richard
    : :
    : : The way I see it... Well, it's all pretty blurry
    :
    : I'm interested to see the implementation too. But couldn't find the
    : definition of rand() function. Can you please tell where can I find
    : the implementation of rand()?
    : --
    : ~Donotalo()

    I take it you downloaded the Win32 platform SDK? If you search through the rand.c file you can find the implementation.
    To make it easier for you:
    [code]
    /***
    *rand.c - random number generator
    *
    * Copyright (c) 1985-2001, Microsoft Corporation. All rights reserved.
    *
    *Purpose:
    * defines rand(), srand() - random number generator
    *
    ******************************************************************/

    ...

    int __cdecl rand (
    void
    )
    {
    #ifdef _MT

    _ptiddata ptd = _getptd();

    return( ((ptd->_holdrand = ptd->_holdrand * 214013L
    + 2531011L) >> 16) & 0x7fff );

    #else /* _MT */
    return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
    #endif /* _MT */
    }
    [/code]
    There's the basic multiplication, but also an addition, and after that the lower 16 bits are discarded, and the higher 16 are used.

    Best Regards,
    Richard

    The way I see it... Well, it's all pretty blurry
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories