# 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()

• 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
*
*
*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