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:

#include<iostream>
#include<ctime>
#include<cstdlib>
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;
}

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:
:

: 
: #include<iostream>
: #include<ctime>
: #include<cstdlib>
: 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;
: }
: 

:
: 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() range. 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() range.
: 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:

/***
*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 */
}

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