CODEWITHSUNDEEP
c++randomsrand
Luke
Luke

Reputation: 7210

Why does rand() produce the same value when seeded with 1 and UINT_MAX?

Here's some code:

#include <iostream>

int main() {
    srand(1);
    std::cout << rand() << "\n";
    srand(UINT_MAX);
    std::cout << rand() << "\n";
}

This produces the following output:

16807
16807

Why do these two seeds produce the same result? The entire sequence of values they produce on successive rand() calls is also identical. The range of possible values is too large for this to be a pure coincidence. Is it:

(Possibly related: the seeds 10, 100, 1000, 10000, and 100000 produce 168070, 1680700, 16807000, 168070000, and 1680700000 respectively.)

Upvotes: 5

Views: 549

Answers (5)

anatolyg
anatolyg

Reputation: 28269

A very simple usable random number generator is a Lehmer number generator. This RNG is maybe the simplest to implement in software, which is still usable, so probably it has the most issues with randomness, and most easy to analyze.

The number 16807 (aka the fifth power of 7) is associated with Lehmer RNG, because it was used in one of the earliest implementations in 1988 - apparently still in use today!

The formula for Nth random number is (using ^ for exponentiation):

R(n) = (seed * (16807 ^ n)) mod (2 ^ 31 - 1)

If you set seed = 1, n = 1:

R(1) = 16807 mod (2 ^ 31 - 1) = 16807

If you set seed = 2 ^ 32 - 1:

R(1) =
    (2 ^ 32 - 1) * 16807 ≡ (expressing 2^32 = 2^31 * 2)
    ((2 ^ 31 - 1) * 2 + 1) * 16807 ≡ (distributive law)
    (2 ^ 31 - 1) * 2 * 16807 + 1 * 16807 ≡ (modulo 2^31-1)
    16807

Here the equality of the first number in the random sequence is because the modulo-number in the Lehmer RNG is almost a power of 2 (2^31-1), and your seed is also almost a power of 2 (2^32-1).

The same would happen for seed = 2^31.

Upvotes: 4

peterchen
peterchen

Reputation: 41106

tl;dr: rand() is known to be that bad.

The actual values are implementation defined. I get the following values on my platform:

seed:          1 : 41
seed: 4294967295 : 35
seed:         10 : 71
seed:        100 : 365
seed:       1000 : 3304
seed:      10000 : 32694

rand() can be relied on to look somewhat random to a casual user in a hurry. It is not portably suitable for anything else.

The implementation usually use a low quality generator (most often Linear Congruential with bad constants).

The required numeric range is 0...32767, and while implementation may they usually don't exceed that - so you can expect many seeds to result in the same value.

For C++ modern, see <random> for reliable options.

Upvotes: 3

eerorika
eerorika

Reputation: 238381

I don't see a good reason why the unfortunate correlation that you observed would be designed into the implementation of rand that you're using. It's most likely an accident of the implementation as you suggest. That said, I would also consider it a coincidence, that you can produce correlation with exactly those inputs. Another implementation could have other sets of unfortunate inputs.

if so, I'm curious what that might be

If your implementation is open source, then you can find out by reading the source. If it's proprietary you could still find a mention of the algorithm in some documentation, or if you're a customer, you could ask the implementer.

Upvotes: 0

jofel
jofel

Reputation: 3405

This depends on the implementation of you random number generator. See What common algorithms are used for C's rand()? for common implementations.

Usually the space of possible seed values is much shorter than your UINT_MAX. It could be that 1 and UINT_MAX are mapped to the same internal seed.

Often Linear congruential generator are used for rand(), then the first generated random number depends like

first_random_number  = (seed * const + another_const)  % third_constant

on the seed. This explains the dependence you found.

Upvotes: 2

Michael
Michael

Reputation: 1035

As stated here, If seed is set to 1, the generator is reinitialized to its initial value and produces the same values as before any call to rand or srand.

Also note that Two different initializations with the same seed will generate the same succession of results in subsequent calls to rand.

Upvotes: -3

Related Questions