rand() questions - Programmers Heaven

Howdy, Stranger!

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

Categories

rand() questions

DonotaloDonotalo Posts: 715Member
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

  • LundinLundin Posts: 3,711Member
    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.
  • AllAboutCPPAllAboutCPP Posts: 1Member
    You can check my web site about some information about rand()

    http://cpp-knowledgestore.blogspot.com/
  • DonotaloDonotalo Posts: 715Member
    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()
  • BitByBit_ThorBitByBit_Thor Posts: 2,444Member
    : 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
  • LundinLundin Posts: 3,711Member
    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.
  • BitByBit_ThorBitByBit_Thor Posts: 2,444Member
    : 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
  • DonotaloDonotalo Posts: 715Member
    : 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()
  • BitByBit_ThorBitByBit_Thor Posts: 2,444Member
    : : 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.