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

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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.