C++ Predictable Rand() Output

问题:

After noticing that the rand() function produced the same output of 41 each time, I seeded the generator using srand(time(0)). That solved the problem of the recurring output but now it's giving me constantly increasing numbers. (I.E. 245, 248, 250, 253, 255, 256). I can understand that it is increasing because of the influence by the system time but is this normal?

Here is my program:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main()
{

    int number;

    srand(time(0));

    cout << rand() % 1000;

    return 0;

}

I am running this repeatedly and not in a loop. Outputs of multiple trials: 285 295 305 311 325 334 344 354 355

回答1:

C++ rand() from MS uses the simplest random generator Linear congruential generator

This is the code for it:

int __cdecl rand (
    void
    )
{
    _ptiddata ptd = _getptd();

    return( ((ptd->_holdrand = ptd->_holdrand * 214013L
        + 2531011L) >> 16) & 0x7fff );
}

So whenever you seed your function you just set the first value (which obviously increases just by some units from time to time if you run your program fast)

Now if you plug in your math equation of the rand() a value x+a where x is the value with which your function was called last time and a is the variation of your time since that call you will notice: ((x+a) * 214013 + 2531011) >> 16 = (x*214013+2531011 + a*214013) >> 16

Since you run your program very fast. Your a varies between 0 and 5 sec let's say. Then your a*214013 has a max value of 1070065 now when you right shift this number by 16 bits you end up with 16 in decimal and this is approximately how much your new output differs from your previous one (I say approximately because you can not say that (x*214013+2531011 + a*214013) >> 16 = (x*214013+2531011 >> 16) + (a*214013 >> 16) because of the carries)

回答2:

This bug comes up about once a week here:

If you call srand() every time before you call rand(), then you're not getting random numbers at all, you're getting a hash function of the time. Call srand() ONCE, AND ONLY ONCE, outside the loop, preferably at the very start of your program, then call rand() as many times as needed to get values.

There's no such thing as generating "one random number". If you need random numbers over a series of program invocations, you have no choice but to generate those random numbers outside the program. One way to do that is to read from /dev/urandom (on Linux) or use CryptGenRandom (on Windows). Another option is to use hardware, or a service like random.org.

It doesn't matter how good a generator you have--if you seed every call, you're not getting random numbers, you're getting a hash function of the seed value. If your seed value changes fast enough, and the hash function is very good, that might be good enough--but it's still not using the RNG algorithm at all.

回答3:

I have no idea why you are getting those results, but there are better ways in C++11:

#include <random>
#include <iostream>
int main()
{
    auto rnd = std::default_random_engine(std::random_device{}());
    std::uniform_int_distribution<> dis(1, 999);
    std::cout << dis(rnd) << '\n';
}

回答4:

rand is implemented as a linear congruential generator in runtime libraries and this has the form:

result = (seed * result + offset) % big_number

If we consider big_number to be infinity and you run your program at time t you get

result = t * result + offset

If you run the program again after a very short period alpha you get

result = (t + alpha)* result + offset

If the runtime library initializes result with a small value, the displayed result would increment with the small value of alpha * result.

Replacing time() with a higher resolution counter would greatly improve this. For example on x86, rdtcs instruction (often available as a compiler intrinsic) would almost solve the issue.

A better solution is to use a non-linear congruential generator to seed rand() like the one suggested by Jesse Good which is also available on non-c++11 compiler through boost library.

When possible, it's better to stick with c++11 random generators rather than c rand.

回答5:

The way rand works is you need to follow two rules:

1. you must seed it first (srand) and
2. you don't want to seed it before every call to rand. You are just to seed it once before your entire sequence.

So to really test it you, your code should look more like this:

int main()
{
    srand(time(0));

    // Output a sequence of 100 random numbers, each less than 1000
    for ( int i = 0; i < 100; i++ )    
        cout << rand() % 1000 << endl;

    return 0;
}

If the program by necessity only outputs one random number each run and the program runs as often as once per second or more, then time(0) may not be a suitable seed. Perhaps using clock_gettime(3) which will give you something more in the milliseconds.

回答6:

I recently ran across the same problem and found that Karoly Horvath's comment on your original question solved the issue, although it is a bit "hacky". I was seeing a predictable increase in return values, and after sticking another rand() immediately after the srand(), the problem went away. I ended up with this:

srand(time(NULL));
rand();
int seed = rand();

I'd like to figure out why this is happening...but in the meantime this works.