Random Number Generator in C

Question

I'm trying to generate a random number 0 - 59, and am not satisfied with the rand() function in C. Here is the code I'm playing around with:

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

main()
{

int num;
srand(time(NULL));
num = rand();
num = num % 59;
printf("%d\n", num);
}

I've repeated the run on this code and noticed that the random numbers being generated don't really seem that random. The generated numbers produced are definitely following a pattern, as each time I run the program the number gets progressively larger until it wraps back around to the beginning (i.e. 2, 17, 21, 29, 38, 47, 54, 59, 4, 11....etc).

Is there a way I can seed the function so that every time I re-run the function I get a true random number with a 1/60 chance of being generated? Or are there any alternative methods I can implement myself rather than using the rand() function in C?

Don't use `%` to restrict the range of pseudo-random numbers: http://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator — Sinan Ünür, Aug 15 '13 at 14:05
Here is another way to generate your numbers, that seems to match your need: http://stackoverflow.com/questions/14441680/is-it-modern-c-to-use-srand-to-set-random-seed — roky, Aug 15 '13 at 14:10
Don't try to implement your own generator. Assuming this is for statistical purposes rather than crypto, do a google search for "Mersenne Twister". — pjs, Aug 15 '13 at 14:13
Generating a single random number from each of a variety of seeds is essentially testing the randomness of your seed sequence, not the PRNG. Changing the PRNG will not change the seed sequence or its entropy. — Casey, Aug 15 '13 at 14:42

score 7 · Answer 1 · 2013-08-15T15:19:05.927

7

Is there a way I can seed the function so that every time I re-run the function I get a true random number

No, the C standard library uses a PRNG (pseudorandom number generator). You will never get true random numbers.

You can, however, seed it with something that changes more frequently than time(), for example, on POSIX:

struct timeval tm;
gettimeofday(&tm, NULL);
srandom(tm.tv_sec + tm.tv_usec * 1000000ul);

Also, using the modulo operator for generating a random number is not a good solution (it severely decreases entropy). If you have a BSD-style libc implementation, use

uint32_t n = arc4random_uniform(60);

Or, if you don't have this function:

// random() is guaranteed to return a number in the range [0 ... 2 ** 31)
#define MAX_RANDOM ((1 << 31) - 1)

long n;

do {
    n = random();
} while (n > (MAX_RANDOM - ((MAX_RANDOM % 60) + 1) % 60));
n %= 60;

Note the use of random() - it is superior to rand() (which had and has a number of low-quality implementations). This function can be seeded using srandom().

Or are there any alternative methods I can implement myself rather than using the rand() function in C?

You can (of course, else how would the writers of the C library implementation do it?), but you better not - it's a separate science to write a good PRNG, so to say.

edited Aug 15 '13 at 15:19

answered Aug 15 '13 at 14:10

The fundamental problem with `%` is that it tries to fit 2**n equiprobable beads into 60 buckets. How is `rand() / (double)RAND_MAX * 60` any better? – Pascal Cuoq Aug 15 '13 at 14:15
@PascalCuoq Is it not? If you use modulo division, the chance of getting numbers between 0 and `60 - (2 ** n % 60)` is higher. AFAIK this problem is not present when you exclude the modulus operation, since the problem is caused by the fact that `2 ** n` may not be divisible by 60. – Aug 15 '13 at 14:20
1

Well, the fact that `2 ** n` is not divisible by 60 is exactly the problem, and with `/ (double)RAND_MAX * 60` you are still sending these `2 ** n` equiprobable values to 60 buckets in a deterministic way. It is not the same buckets that get more beads, but mathematically, some buckets still get more beads. – Pascal Cuoq Aug 15 '13 at 14:23
@PascalCuoq So did I just run into [this](http://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator#comment14490185_10989061)? (If so, I'm editing my answer.) – Aug 15 '13 at 14:25
Yes. If you get beads 2**n at a time, the only way to fill 60 buckets equally is to either throw away some beads, or to request another set of 2**n beads, or a mix of both these actions. – Pascal Cuoq Aug 15 '13 at 14:31
@PascalCuoq Edited, I hope it's good now. – Aug 15 '13 at 14:41
It doesn't set `n` to a number below 60. Try `long N = MAX_RANDOM / 60; do { n = random() / N ; } while (n >= 60);` (untested) – Pascal Cuoq Aug 15 '13 at 14:50
@PascalCuoq Sorry, I don't understand, now what's the problem? – Aug 15 '13 at 14:52
With the current code, `n` is not set to a value in the interval 0-59. That was the original question. – Pascal Cuoq Aug 15 '13 at 14:53
@sh1 What do you suggest instead? – Aug 15 '13 at 15:14
@PascalCuoq Ah, I see. I forgot the modulus. – Aug 15 '13 at 15:19

score 1 · Answer 2 · answered Aug 15 '13 at 14:47

The way your program is written, you must re-run it each time to get a new random number, which also means it gets re-seeded each time. Re-seeding a PRNG is bad.

You want to seed once, then generate a bunch of random numbers.

Do it this way:

int main(void)
{
    int num, i;
    srand(time(NULL));  // Seed ONCE

    for(i=0; i<100; ++i) // Loop 100 times for random numbers
    {
        num = rand();
        num = num % 59;
        printf("%d\n", num);
    }
}

Now you should get much better results.

sh1 · Answer 3 · 2013-08-15T15:11:31.797

Each time you re-run the program, you re-seed with time(), and that function only advances once a second (if you re-run the program quickly enough you'll get the same result).

The fact that it seems to increment until it rolls over suggests that the first call to rand() is returning the un-modified seed -- that number which increments once per second. In that case you're getting the same results (or very similar results) as if you'd run:

printf("%d\n", time(NULL) % 59);

I'm sure you can see what's wrong with that.

In this case, if you used the 'more correct' rand() * 59 / RAND_MAX, which is meant to prefer a value from the 'more random' bits, you would have an even worse situation -- the results wouldn't change at all for maybe 500 seconds, or more.

Fundamentally you need to find a less predictable seed, but you may also want to see that it's properly mixed before you use it.

Reading from /dev/urandom should provide a good seed, in which case you won't need to worry about mixing, but otherwise calling rand() a couple of times should help to do away with the especially glaring artefacts of the low-quality seed you started with (except, of course, the problem that it only changes once a second).

Random Number Generator in C

3 Answers3

Linked