Implementing Random Number Library

[deeisenberg]

I have been developing a program for some research I'm doing which requires the use of a random number generator. I don't need anything extremely complex or good which is why I was using the rand() function built into C. I have found however that I need more than a 16-bit number (I need at least 100000 different possible integers to have precision in comparing the random numbers to a probability). I found the 32-bit KISS random number generator that is posted on libRNG and it seems like it would suit my needs. The problem is that I really have very little experience programming and don't understand the README file. I don't know how to use the functions in it. I really just need to know what I have to do to set the seed and generate random numbers which I'll put into a string or array. I realize that the solution is probably pretty simple and that I should understand but I would really appreciate the help.

[javaeyes]

If you're on a 32 bit system then:

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

should give you psuedo-random numbers up to 4,294,967,295
I think.

[laserlight]

Heh, so much for KISS. Anyway, you are trying to use a PRNG rather than implement one. Mersenne Twister is a popular PRNG. Its reference implementation can be found at: Mersenne Twister with improved initialization.

To use it, copy the entire mt19937ar.c except the main function. Create a header file like this:

#ifndef MERSENNE_TWISTER_H_
#define MERSENNE_TWISTER_H_

void init_genrand(unsigned long s);
unsigned long genrand_int32(void);

#endif

Then include this header and use init_genrand like you use srand and use genrand_int32 like you use rand. You just need to compile and link your modified mt19937ar.c with the rest of your program.

If you're on a 32 bit system then:

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

should give you psuedo-random numbers up to 4,294,967,295

No, RAND_MAX does not have to coincide with UINT_MAX.

[javaeyes]

Laser is the pro, do what she says.

[oogabooga]

rand() is actually 15 bits (RAND_MAX is usually, sadly, 32767 = 0x7fff). If you really don't need it to be that "good", then you could simply double up on rand, something like this:

/* Returns 30 random bits: range [0, 1073741823] */
int rnd30() {
    return rand() << 15 | rand();
}

Remember to call srand(time(0)) ONCE AND ONLY ONCE in your program before calling rnd30.

[laserlight]

rand() is actually 15 bits (RAND_MAX is usually, sadly, 32767 = 0x7fff).

RAND_MAX is guaranteed to be at least 32767, but on some somewhat commonly used implementations it is much greater than that.

If you really don't need it to be that "good", then you could simply double up on rand

Good idea, but you'll need to check the value of RAND_MAX first or risk undefined behaviour from the left shift on a signed integer.

[oogabooga]

RAND_MAX is guaranteed to be at least 32767, but on some somewhat commonly used implementations it is much greater than that.

True, I have seen that and was very pleasantly surprised. But on gcc4.6.1 and MSVC2010 it still seems to be the puny 32767.

you'll need to check the value of RAND_MAX first or risk undefined behaviour from the left shift on a signed integer.

Right, so I should have posted something like this:

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

#if RAND_MAX != 32767
#error RAND_MAX must be 32767 for this code to work
#endif

/* Returns 30 bits: range [0, 1073741823] */
int rnd30(void) {
    return (rand() << 15 | rand());
}

int main(void) {
    int i;
    srand(time(0));
    for (i = 0; i < 100; i++)
        printf("%d\n", rnd30() % 100000);
    return 0;
}

Of course this doesn't deal with the extra probability of the lower numbers, but the OP doesn't seem to concerned (and in the above case, with a modulus of 100000, the lower 41824 numbers, incl. 0, have only a 0.09% greater change of appearing).

Actually, I did have a more complicated scheme that throws away the lower 2 bits of rand()'s return value (because they are supposedly less random then the other bits) and also includes a loop to get rid of that extra probability of lower numbers:

/* Random 26 bits: range [0,67108863] */
int rnd(int n) {
    int limit = 67108863 / n * n;
    int r;
    do
        r = rand() >> 2  | (rand() & 0xfffc) << 11;
    while (r > limit);
    return r % n;
}

// Since it includes the modulus, call it like:
r = rnd(100000);

[phantomotap]

With widely available implementations of very good PRNGs available taking the time to glue `std::rand' into something with guesswork is silly.

That said, if you are going to do it, sample multiple calls without tossing bits away (potential entropy) and mix them thoroughly (multiple overlapped xor and addition with prime rotation for example).

Soma

[laserlight]

But on gcc3.4.5 and MSVC2010 it still seems to be the puny 32767.

I think it is a matter of the MSVCRT being used (assuming the MinGW port of gcc 3.4.5; with Cygwin things may be different).

throws away the lower 2 bits of rand()'s return value (because they are supposedly less random then the other bits)

This might be futile since you don't actually know what is the PRNG algorithm used for rand. Personally, I feel that rather than mess up the research by risking a failure to combine the numbers generated in an appropriate way, deeisenberg might as well use a tested implementation of a well known PRNG that has seen use for simulations in research, hence my suggestion of Mersenne Twister's reference implementation.

[oogabooga]

I agree. I went overboard here! If you want something cheap with rand, then the first thing I posted is the thing to do. But obviously it's best to simply get a decent PRNG and use that.

[deeisenberg]

Heh, so much for KISS. Anyway, you are trying to use a PRNG rather than implement one. Mersenne Twister is a popular PRNG. Its reference implementation can be found at: Mersenne Twister with improved initialization.

To use it, copy the entire mt19937ar.c except the main function. Create a header file like this:

#ifndef MERSENNE_TWISTER_H_
#define MERSENNE_TWISTER_H_

void init_genrand(unsigned long s);
unsigned long genrand_int32(void);

#endif

Then include this header and use init_genrand like you use srand and use genrand_int32 like you use rand. You just need to compile and link your modified mt19937ar.c with the rest of your program.


No, RAND_MAX does not have to coincide with UINT_MAX.

I did this, the run time is good but I am getting ~50% negative and ~50% positive numbers when I access the random numbers from the string I put them in.

[laserlight]

I did this, the run time is good but I am getting ~50% negative and ~50% positive numbers when I access the random numbers from the string I put them in.

And the problem is...?

[Cynic]

I did this, the run time is good but I am getting ~50% negative and ~50% positive numbers when I access the random numbers from the string I put them in.

50/50 on a pseudo-random number generator. Sounds pretty good to me.

[oogabooga]

If you're calling this function:
unsigned long genrand_int32(void);
then you shouldn't be getting signed numbers at all. Remember to make the number you are storing the return value in an unsigned long. You say you're putting the number into a string. If you're doing that with sprintf then remember to use %lu and not %ld (or %li).