Hi everyone, sorry if this has been answered before - I caught a whiff of a
discussion about c's rand() function in a mailing list archive, but
couldn't
find a definitive answer.
I'm trying to do a simple CS project on my machine where I generate two sets
of values in parallel using rand() and am running into infinite loops of
values, and couldn't figure out why, so I wrote a test program:
#include <iostream>
#include <cstdlib>
#include <ctime>
int main()
{
int a, b;
srand((unsigned)time(0));
for (int i=0 ; i < 50 ; i++)
cout << rand() % 32 << " " <<
rand() % 4 << endl;
return 0;
}
No matter how many times I run this it seems to alternate between generating
two different but non-unique sets of values, depending on whether time(0) is
even or odd..and I can't understand why (values at the end of this message).
My uname -a is:
FreeBSD repose 4.8-RC FreeBSD 4.8-RC #0: Mon Mar 24 09:13:35 CST 2003
timothy@repose:/usr/obj/usr/src/sys/Repose i386
It seems like the consensus on the thread I read was to use /dev/random or
/dev/urandom..but this isn't really an option for a CS project a TA has to
grade, so I've had to SSH out to finish the project. I just want to know
what I'm doing wrong, and why I can't do this on my FreeBSD machine =\
The two value loops are:
22 1
4 3
2 1
16 3
14 1
28 3
26 1
8 3
6 1
20 3
18 1
0 3
30 1
12 3
10 1
24 3
22 1
4 3
2 1
16 3
14 1
28 3
26 1
8 3
6 1
20 3
18 1
0 3
and
19 2
9 0
15 2
5 0
11 2
1 0
7 2
29 0
3 2
25 0
31 2
21 0
27 2
17 0
23 2
13 0
19 2
9 0
15 2
5 0
11 2
1 0
7 2
29 0
3 2
25 0
31 2
21 0
27 2
17 0
23 2
13 0
19 2
Thanks for any insight you can lend.
At 09:01 07/04/2003 -0500, Eric Timme wrote:>No matter how many times I run this it seems to alternate between generating >two different but non-unique sets of values, depending on whether time(0) is >even or odd..and I can't understand why (values at the end of this message). >[...] I just want to know >what I'm doing wrong, and why I can't do this on my FreeBSD machine =\$ man rand RAND(3) FreeBSD Library Functions Manual RAND(3) NAME rand, srand, rand_r - bad random number generator ^^^^^^^^^^^^^^^^^^^^^^^^^^^ You're not doing anything wrong; rand(3) is explicitly defined to be a bad random number generator. If you want a slightly better random number generator for non-cryptographic purposes, you could use random(3). Colin Percival
On Mon, Apr 07, 2003 at 09:01:20AM -0500, Eric Timme wrote:> No matter how many times I run this it seems to alternate between generating > two different but non-unique sets of values, depending on whether time(0) is > even or odd..and I can't understand why (values at the end of this message).In each case you are only looking at the low order bits of the number, which will always be particularly bad. The simple linear congruence generators used for rand have the form: seed = seed * 1103515245 + 12345 return seed % (RAND_MAX+1) where RAND_MAX+1 is a power of two. Since you're looking at this mod 32 (and mod 4) it becomes somthing like: seed = seed * 13 + 25 return seed % 32 where seed is effectively now a number between 0 and 31. This can't have a period of longer than 32 calls. Rather than use rand()%32 you might want to use something like (rand()+RAND_MAX/64)/(RAND_MAX/32) - using the high order bits means that you are not effectively reducing the side of the state space. David.
On Mon, Apr 07, 2003 at 03:16:03PM +0100, David Malone wrote:> Rather than use rand()%32 you might want to use something like > (rand()+RAND_MAX/64)/(RAND_MAX/32) - using the high order bits means > that you are not effectively reducing the side of the state space.Or use a better PRNG like arc4random(). Kris -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 187 bytes Desc: not available Url : http://lists.freebsd.org/pipermail/freebsd-stable/attachments/20030407/18634c30/attachment.bin
Eric Timme (by way of Eric Timme ) wrote:> Hi everyone, sorry if this has been answered before - I caught a whiff of a > discussion about c's rand() function in a mailing list archive, but couldn't > find a definitive answer. > > I'm trying to do a simple CS project on my machine where I generate two sets > of values in parallel using rand() and am running into infinite loops of > values, and couldn't figure out why, so I wrote a test program: > > #include <iostream> > #include <cstdlib> > #include <ctime> > > int main() > { > int a, b; > srand((unsigned)time(0)); > > for (int i=0 ; i < 50 ; i++) > cout << rand() % 32 << " " << rand() % 4 << endl; > > return 0; > } > > No matter how many times I run this it seems to alternate between generating > two different but non-unique sets of values, depending on whether time(0) is > even or odd..and I can't understand why (values at the end of this message). > > My uname -a is: > FreeBSD repose 4.8-RC FreeBSD 4.8-RC #0: Mon Mar 24 09:13:35 CST 2003 > timothy@repose:/usr/obj/usr/src/sys/Repose i386 > > It seems like the consensus on the thread I read was to use /dev/random or > /dev/urandom..but this isn't really an option for a CS project a TA has to > grade, so I've had to SSH out to finish the project. I just want to know > what I'm doing wrong, and why I can't do this on my FreeBSD machine =\If using random() is truely out of the question, you might try using some of the other bits in the returned number. The results wont' be very random, but at least they won't be annoyingly cyclic. Something like: cout << ( rand() >> 5 ) % 32 << " " << ( rand() >> 5 ) % 4 << endl; You should be aware that FreeBSD isn't the only platform with a lousy rand() function. There is a good chance the rand() on your TA's machine is going to return results like this as well. You may want to use configure if possible to test for the existence of a better random number generator, and use that instead if possible. -- \ |_ _|__ __|_ \ __| Jason Andresen jandrese@mitre.org |\/ | | | / _| Network and Distributed Systems Engineer _| _|___| _| _|_\___| Office: 703-883-7755