srand/rand slowly changing starting value

Question

I have written a simple BASIC interpreter that I'm running on Clang/macOS. To implement RND(), desiring to use as standard C as possible, I used srand/rand. Near the start of the program (in retrobasic.c) I call srand (yes, once) with either null or a user-passed value:

if (random_seed > -1)
  srand(random_seed);
else
  srand(time(NULL));

There is only one place that a number is produced:

result.number = ((double)rand() / (double)RAND_MAX); 

The code that's calling this is INT(RND()*25)+1 and I noticed it returns the same starting number every run, but it changes every hour or so. So last night it was always 25, this morning was 2, and now it's 3. I put a printf("%d", rand()); right after the srand. Sure enough, that gets me:

200829549  
200964005  
201098461  
201232917  
201703513

That seems to be pseudo-seconds in the 3rd/4th digits, which explains the behaviour I'm seeing. This added printf "fixes" it by pumping the sequence and then any subsequent calls to rand are fine. I would really like to understand/solve this the right way.

Clang complains about the srand(time(NULL)), saying it takes an unsigned int and wants me to cast the time_t to silence the warning. time_t is implementation dependant, but I suspect it is really a unsigned long? Perhaps this is an issue with a 32/64 bit conversion going into srand? I found a few tantalizing posts, like this one, but no ultimate conclusion.

This is not about bad random sequence, the sequence is fine (for my needs). There are threads that are about bad starting numbers, but invariably they end up being improper srand use. Does anyone have a suggestion here?

Answer 1

time_t can be a floating point type which could explain why the seed only changes every now and then. If time_t holds days since some starting time point where the fraction describes the time of day, you'd only see a new seed once every day.

You could try using timespec_get (requires at least C11). The nanosecond part of the struct timespec is specified to be a long so a cast to unsigned will work fine:

#include <stdlib.h>
#include <time.h>

void seeder() {
    struct timespec ts;
    timespec_get(&ts, TIME_UTC);
    srand((unsigned ) ts.tv_nsec);
}

int main(void) {
    seeder();

    // ...
}

Answer 2

The effect you describe suggests that the highest-order bits of the output of your system's rand() are insensitive to the lowest-order bits of its internal state (which you initialize via srand()). From your "every hour or so", I speculate that you may need a difference at bit 12 or higher, corresponding to 4096 s or about 68 minutes, to overcome that effect.

This added printf "fixes" it by pumping the sequence and then any subsequent calls to rand are fine.

That would be consistent. Although the first numbers pulled from the generator on runs performed close together may have similar values, the effects on the PRNG's internal state will be different enough that subsequent results then diverge.

A simple solution, then, might be simply to discard a couple of initial results from rand(), immediately after the srand() call:

if (random_seed > -1) {
  srand(random_seed);
} else {
  srand(time(NULL));
}
rand();
rand();

Alternatively, any approach that causes your seeds to differ more widely is likely to help even with the initial numbers. @SteveSummit's idea of combining the PID with the output of time(NULL) could be that, especially if you shift or rotate the PID as he suggested.^* For example, something like

    unsigned int my_pid = getpid();
    unsigned int random_seed = ((unsigned int) time(NULL)) ^ (my_pid << 8);

    // ...

You could go further to get initial seeds that vary more randomly, but my reading of the question suggests that either of the above would be adequate for your needs. And they are not mutually exclusive, of course.

---

^*But note that getpid() and PIDs in general are not native to C. They are POSIX features, so they may not themselves be suitable for your use if you want to rely only on the language spec.

Answer 3

The fundamental problem here is that the standard library function rand(), basically, sucks.

I tested your situation with this code fragment:

printf("   seed         r      number  r2\n");
for(int i = 0; i < 10; i++) {
    int seed = my_time(NULL);
    srand(seed);
    int r = rand();
    double result_number = ((double)r / (double)RAND_MAX); 
    int rr = (int)((result_number*25)+1);
    printf("%d %d %f %d\n", seed, r, result_number, rr);
}

I used a function my_time() so that I could precisely control the way that the standard time function yields values that exactly increment once per second:

time_t my_time(time_t *tp)
{
    static time_t t = 1685535843;
    if(tp != NULL) *tp = t;
    return t++;
}

And since I happen to be on a Mac, it turned out that I could reproduce your surprising result:

   seed         r      number  r2
1685535843 1344125724 0.625907 16
1685535844 1344142531 0.625915 16
1685535845 1344159338 0.625923 16
1685535846 1344176145 0.625931 16
1685535847 1344192952 0.625939 16
1685535848 1344209759 0.625946 16
1685535849 1344226566 0.625954 16
1685535850 1344243373 0.625962 16
1685535851 1344260180 0.625970 16
1685535852 1344276987 0.625978 16

Not very random!

It's pretty well known that a simplistic linear congruential random number generator, which is what many versions of rand() tend to use, has poor randomness properties. The standard problem with such generators is that the low-order bits tend to be cyclic, not random, such that if you take, say, rand() % 2, you'll get an exactly alternating (totally non-random) sequence of 0, 1, 0, 1, 0, 1, ... . I hadn't encountered the problem we're having here, namely that the high order bits seem to be strongly correlated — on the first call, at least — with an srand-provided seed.

There are a number of ways around this. In a comment I suggested adding in some more entropy, perhaps via a call to getpid:

seed = my_time(NULL) + my_getpid()

Again I emulated getpid for total predictability:

int my_getpid()
{
    static int pid = 12345;
    return pid++;
}

But this doesn't help at all, because there's still far too much order in the seeds:

   seed         r      number  r2
1685548188 1551608139 0.722524 19
1685548190 1551641753 0.722539 19
1685548192 1551675367 0.722555 19
1685548194 1551708981 0.722571 19
1685548196 1551742595 0.722586 19
1685548198 1551776209 0.722602 19
1685548200 1551809823 0.722618 19
1685548202 1551843437 0.722633 19
1685548204 1551877051 0.722649 19
1685548206 1551910665 0.722665 19

I'm out of time (I'll update this answer later), but other things you can try are:

1. use more and better entropy in your seed
2. burn a few random numbers after calling srand (hey, it works in Vegas!)
3. use random() instead of rand()