Ben Pfaff wrote:

"Jack" <js*********@yahoo.com> writes:

When I use rand(), is the RAND_MAX value how long I am guaranteed that

the same value will not appear twice?

No. It is very unlikely that no value will appear twice. If the

random number generator is uniformly random, the chance that no

value will appear twice in RAND_MAX calls, assuming RAND_MAX ==

32767, is

(32766 / 32767) * (32765 / 32767) * ... * (1 / 32767)

== 32766! / (32767)**32766

~= 1.347 * 10**-14228 (according to Emacs calc)

This result is much, much smaller than the maximum value for

LDBL_MIN.

(Someone should check my math, I'm not so good at this. Also,

smartasses, the above are math formulas, not C expressions.)

FWIW, a different tool gives me the same result. If we're

wrong, I at least am in good company.

However, this calculation assumes successive rand() values

are independent, which is certainly not the case. rand() is

required to be deterministic in the sense that it produces the

exact same sequence of values for a given explicit or implied

srand() argument; the srand() argument completely determines

the sequence of subsequent rand() values.

Drifting into implementation specifics, it is also worth

noting that if rand() is a full-period linear congruential

generator it produces a permutation of { 0 .. RAND_MAX }, so

the probability of a repeated value in RAND_MAX calls or even

in RAND_MAX+1 calls is zero! Of course, the probability of a

repetition in RAND_MAX+2 calls rises abruptly to unity. For

a pure multiplicative generator with prime modulus, the generated

values are a permutation of { 1 .. RAND_MAX } and the probability

transition lies between RAND_MAX and RAND_MAX+1 calls.

For the benefit of the O.P. (Ben already knows this), the

Standard does not specify what algorithm underlies rand(), and

different implementations use different generators. It is

certainly an error to assume that rand() will not repeat itself

within RAND_MAX calls; it is even possible that two rand() calls

in a row can return the same value.

--

Eric Sosman

es*****@acm-dot-org.invalid