Long random numbers in C

Question

My problem is really simple (silly, maybe). I need a long random number using the C language as simple as possible. I researched through out the internet and coudn't find anything that could help me. The only thing I could find was that the rand() function cannot handle numbers bigger than 32,767.

Here is part of my code, and the long number should be between 0 and 1,000,000:

#include <stdio.h>
#include <time.h>
#include <conio.h>

#define MAX 999999

void main()
{
    int i;

    printf("\n Just a test with random numbers.");

    printf("\n ------------------------------------\n\n");

    srand(time(NULL));

    for(i = 0; i < 50; i++)
    {
        printf(" %li\n", rand() % MAX+1);
    }

    printf("\n ====================================\n");
    getch();
}

Answer 1

You can build bigger numbers by OR:ing together several calls to rand().

#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define LIMIT (1000000)

static uint16_t highest_bit(uint64_t v) {
    uint16_t out = 0;
    while (v > 0) {
        v >>= 1;
        ++out;
    }
    return out;
}

uint32_t myrand() {
    static bool init = 0;
    static uint16_t n;
    static uint16_t shift;
    if (!init) {
        uint16_t randbits = highest_bit(RAND_MAX + (uint64_t)1L);
        uint16_t outbits = highest_bit(LIMIT);
        n = (outbits + randbits - 1)/randbits;
        shift = randbits;
        init = 1;
    }
    uint32_t out = 0;
    for (uint16_t i=0; i<n; ++i) {
        out |= rand() << (i*shift);
    }
    return out % LIMIT;
}

It should be noted that this method will be biased (i.e. all numbers won't have the same probability), and it is definitely not cryptographically secure. If you want that, you shouldn't be using rand() at all.

Here's a little main function to test that all numbers are at least possible to get:

int main() {
    bool* seen = calloc(LIMIT, sizeof(bool));
    if (!seen) {
        fprintf(stderr, "failed to malloc 'seen' array\n");
        return 1;
    }
    uint32_t nseen = 0;
    uint32_t ntries = 0;
    // this could take a long time -- you can use Ctrl-C to abort a command-line program
    while (nseen < LIMIT) {
        if ((ntries & 0xffff) == 0) {
            printf("after %u tries, we've seen %u different numbers.\n", ntries, nseen);
        }
        ++ntries;
        uint32_t r = myrand();
        if (!seen[r]) {
            seen[r] = true;
            ++nseen;
        }
    }
    printf("Found them all after %u tries!\n", ntries);
    return 0;
}

Answer 2

I assume that you want a random number in range [0, 1000000[ that is in a range length of 10⁶.

It is exactly the same as picking two random numbers in range [0, 1000[, one for the high order (decimal) digits, one for the low order ones. But it is much easier to work in that range...

If you want a correct random generation, you should worry for the probability of every possible number and try to keep it as equal as possible. So you must first search the greatest power of 1000 below RAND_MAX, reject all number greater than it and take the modulus 1000 of each kept value.

// Find the max number to keep
int period = 1000
unsigned int max = period;
while (max < (unsigned long) RAND_MAX) {
    unsigned long t = max * period;
    if (t < max) break;  // test for a possible overflow
    max = t;
}

You can then use

for(;;) {
    unsigned long randnum = rand();
    if (randnum < max) {
        randnum %= period;
        break;
    }
}

And when you have two random number in range [0, 1000[, say n1 and n2, just do:

n = period * n1 + n2;

Of course above assume that you have a correct rand function. If unsure use random - rand man page on my system states it uses same algorythm as random that's why I assume I can use it securely, but it also says:

However, on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-order bits. Do not use this function in applications intended to be portable when good randomness is needed. (Use random(3) instead.)

Answer 3

Cryptographical safe long number generator:

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>

unsigned long xorshift(unsigned long state[static 1]) {
    unsigned long x = state[0];
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    state[0] = x;
    return x;
}

long random_long(long min, long max) {
    int urandom = open("/dev/urandom", O_RDONLY);
    unsigned long state[1];
    read(urandom, state, sizeof(state));
    close(urandom);
    unsigned long range = (unsigned long) max - min + 1;
    unsigned long random_value = xorshift(state) % range;
    return (long) (random_value + min);
}

long* random_long_array(long min, long max, int n) {
    long *numbers = (long*) malloc(n * sizeof(long));
    for (int i = 0; i < n; i++) {
        numbers[i] = random_long(min, max);
    }
    return numbers;
}

int main() {
    //FOR TESTING
    long min = 0;
    long max = 5000000;
    int n = 100;
    long *numbers = random_long_array(min, max, n);

    printf("Random number between %ld and %ld:\n%ld\n", min, max, random_long(min, max));

    printf("Random numbers between %ld and %ld:\n", min, max);

    for (int i = 0; i < n; i++) {
        printf("%ld\n", numbers[i]);
    }

    free(numbers);
    return 0;
}

Answer 4

Use random() from <stdlib.h>.

Answer 5

A bad but working solution would be to multiply the result of rand() with MAX / RAND_MAX (I believe there was a constant for this, if not, 32767).

I still think there should be a rand for the larger numbers out there though.

EDIT: Need to typecast the division to float (or double), then back to long.