4-stable and C rand()?

[David Malone]

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.