## C and C++

Moderators: None (Apply to moderate this forum)
Number of posts: 94711

This Forum Only

rand() questions Posted by Donotalo on 19 Nov 2008 at 7:11 PM
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()
Re: rand() questions Posted by Lundin on 20 Nov 2008 at 12:48 AM
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.
Re: rand() questions Posted by AllAboutCPP on 20 Nov 2008 at 8:18 AM

http://cpp-knowledgestore.blogspot.com/
Re: rand() questions Posted by Donotalo on 20 Nov 2008 at 11:27 PM
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()
Re: rand() questions Posted by BitByBit_Thor on 21 Nov 2008 at 2:35 AM
: 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
Re: rand() questions Posted by Lundin on 21 Nov 2008 at 3:23 AM
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.
Re: rand() questions Posted by BitByBit_Thor on 21 Nov 2008 at 4:42 AM
: 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
Re: rand() questions Posted by Donotalo on 21 Nov 2008 at 6:58 AM
: 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()
Re: rand() questions Posted by BitByBit_Thor on 21 Nov 2008 at 7:48 AM
: : 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
*
*
*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

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic