srand(), rand(), RAND_MAX, or XXX weirdness

nazdrowie · 03-07-2005, 09:46 AM

I'm having some problems running the following bitsortgen.c code on my linux machine (you can get it at http://www.cs.bell-labs.com/cm/cs/pearls/code.html -- it's from the book "Programming Pearls" by the way, which is awesome):

Code:

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* bitsortgen.c -- gen $1 distinct integers from U[0,$2) */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 2000000
int x[MAXN];

int randint(int a, int b)
{   return a + (RAND_MAX * rand() + rand()) % (b + 1 - a);
}

int main(int argc, char *argv[])
{   int i, k, n, t, p;
    srand((unsigned) time(NULL));
    k = atoi(argv[1]);
    n = atoi(argv[2]);
    for (i = 0; i < n; i++)
        x[i] = i;
    for (i = 0; i < k; i++) {
        p = randint(i, n-1);
        t = x[p]; x[p] = x[i]; x[i] = t;
        printf("%d\n", x[i]);
    }
    return 0;
}

I get 'Segmentation fault' errors quite often when running the program. I used gdb and ran it a couple times with a break point set at the point where p gets assigned in the second for loop of the main function, and sometimes the p value ends up being negative, hence the seg faults, I guess.

But the odd thing about it is that the program runs just fine on a SunOS -- no problems whatsoever. I've checked it out a bit, and the only difference between the two (Linux and SunOS) that I'm currently aware of is that on my Linux machine RAND_MAX = 2147483647, while on a SunOS machine RAND_MAX = 32767. However, I don't see how that could possibly be causing the problem and resulting in negative p values on a Linux machine.

You can compile the program and see for yourself (run it a couple times and for a couple sets of values). When you run it, just make sure that you pass it two numbers as command-line arguments, with the first one smaller than the second, and the second no larger than 2 million.

Any clues?

Hko · 03-07-2005, 11:28 AM

Quote:

I'm currently aware of is that on my Linux machine RAND_MAX = 2147483647, while on a SunOS machine RAND_MAX = 32767. However, I don't see how that could possibly be causing the problem and resulting in negative p values on a Linux machine.

That's exactly where the problem is. On linux RAND_MAX = 2147483647, which happens to be also the maximum integer value (at least on 32-bits Linux). When you overflow an int variable, it wraps around to negative values. To see this happening, try this:

Code:

int main(int argc, char *argv[])
{
    int p;
    p = 2147483647;  /* max int */
    printf("p = %d\n", p);
    p = p +1;  /* Add 1 */
    printf("p+1 = %d\n", p);
    return 0;
}

So when the randint() function does: RAND_MAX * rand() + rand() it will surely overflow the maximum int value (serveral times at once probably). So you will get about 50% negative values...

You cannot change the maximum value rand() will return (AFAIK). So to fix this change the function to:

Code:

int randint(int a, int b)
{
    return a + (65535 * rand()%65535 + rand()%65535) % (b + 1 - a);
}

or, simpler:

Code:

int randint(int a, int b)
{
    return a + rand() % (b + 1 -a);
}

nazdrowie · 03-07-2005, 12:45 PM

Thank you for the excellent reply!

I suppose I just assumed that: first, the (RAND_MAX * rand() + rand()) computation would be safely handled -- no overflow -- so long as it wasn't cast to an integer first and then used in the computation, and second, that the modulo operator would take care of the rest. It turns out my first assumption was off! Silly rabbit, such tricks aren't for c