implementation of rand()

问题:

I am writing some embedded code in C and need to use the rand() function. Unfortunately, rand() is not supported in the library for the controller. I need a simple implementation that is fast, but more importantly has little space overhead, that produces relatively high-quality random numbers. Does anyone know which algorithm to use or sample code?

EDIT: It's for image processing, so "relatively high quality" means decent cycle length and good uniform properties.

回答1:

Check out this collection of random number generators from George Marsaglia. He's a leading expert in random number generation, so I'd be confident using anything he recommends. The generators in that list are tiny, some requiring only a couple unsigned longs as state.

Marsaglia's generators are definitely "high quality" by your standards of long period and good uniform distribution. They pass stringent statistical tests, though they wouldn't do for cryptography.

回答2:

Use the C code for LFSR113 from L'écuyer:

unsigned int lfsr113_Bits (void)
{
   static unsigned int z1 = 12345, z2 = 12345, z3 = 12345, z4 = 12345;
   unsigned int b;
   b  = ((z1 << 6) ^ z1) >> 13;
   z1 = ((z1 & 4294967294U) << 18) ^ b;
   b  = ((z2 << 2) ^ z2) >> 27; 
   z2 = ((z2 & 4294967288U) << 2) ^ b;
   b  = ((z3 << 13) ^ z3) >> 21;
   z3 = ((z3 & 4294967280U) << 7) ^ b;
   b  = ((z4 << 3) ^ z4) >> 12;
   z4 = ((z4 & 4294967168U) << 13) ^ b;
   return (z1 ^ z2 ^ z3 ^ z4);
}

Very high quality and fast. Do NOT use rand() for anything. It is worse than useless.

回答3:

Here is a link to a ANSI C implementation of a few random number generators.

回答4:

I've made a collection of random number generators, "simplerandom", that are compact and suitable for embedded systems. The collection is available in C and Python.

I've looked around for a bunch of simple and decent ones I could find, and put them together in a small package. They include several Marsaglia generators (KISS, MWC, SHR3), and a couple of L'Ecuyer LFSR ones.

All the generators return an unsigned 32-bit integer, and typically have a state made of 1 to 4 32-bit unsigned integers.

Interestingly, I found a few issues with the Marsaglia generators, and I've tried to fix/improve all those issues. Those issues were:

• SHR3 generator (component of Marsaglia's 1999 KISS generator) was broken.
• MWC low 16 bits have only an approx 2^29.1 period. So I made a slightly improved MWC, which gives the low 16 bits a 2^59.3 period, which is the overall period of this generator.

I uncovered a few issues with seeding, and tried to make robust seeding (initialisation) procedures, so they won't break if you give them a "bad" seed value.

回答5:

I recommend the academic paper Two Fast Implementations of the Minimal Standard Random Number Generator by David Carta. You can find free PDF through Google. The original paper on the Minimal Standard Random Number Generator is also worth reading.

Carta's code gives fast, high-quality random numbers on 32-bit machines. For a more thorough evaluation, see the paper.

回答6:

Mersenne twister

A bit from Wikipedia:

• It was designed to have a period of 2¹⁹⁹³⁷ − 1 (the creators of the algorithm proved this property). In practice, there is little reason to use a larger period, as most applications do not require 2¹⁹⁹³⁷ unique combinations (2¹⁹⁹³⁷ is approximately 4.3 × 10⁶⁰⁰¹; this is many orders of magnitude larger than the estimated number of particles in the observable universe, which is 10⁸⁰).
• It has a very high order of dimensional equidistribution (see linear congruential generator). This implies that there is negligible serial correlation between successive values in the output sequence.

• It passes numerous tests for statistical randomness, including the Diehard tests. It passes most, but not all, of the even more stringent TestU01 Crush randomness tests.

• source code for many languages available on the link.

回答7:

I'd take one from the GNU C library, the source is available to browse online.

http://qa.coreboot.org/docs/libpayload/rand_8c-source.html

But if you have any concern at all about the quality of the random numbers, you should probably look at more carefully written mathematically libraries. It's a big subject and the standard rand implementations aren't highly thought of by experts.

Here's another possibility: http://www.boost.org/doc/libs/1_39_0/libs/random/index.html

(If you find you have too many options, you could always pick one at random.)

回答8:

I found this: Simple Random Number Generation, by John D. Cook.

It should be easy to adapt to C, given that it's only a few lines of code.

Edit: and you could clarify what you mean by "relatively high-quality". Are you generating encryption keys for nuclear launch codes, or random numbers for a game of poker?

回答9:

Better yet, use multiple linear feedback shift registers combine them together.

Assuming that sizeof(unsigned) == 4:

unsigned t1 = 0, t2 = 0;

unsigned random()
{
    unsigned b;

    b = t1 ^ (t1 >> 2) ^ (t1 >> 6) ^ (t1 >> 7);
    t1 = (t1 >> 1) | (~b << 31);

    b = (t2 << 1) ^ (t2 << 2) ^ (t1 << 3) ^ (t2 << 4);
    t2 = (t2 << 1) | (~b >> 31);

    return t1 ^ t2;
}

回答10:

The standard solution is to use a linear feedback shift register.

回答11:

There is one simple RNG named KISS, it is one random number generator according to three numbers.

/* Implementation of a 32-bit KISS generator which uses no multiply instructions */ 

static unsigned int x=123456789,y=234567891,z=345678912,w=456789123,c=0; 

unsigned int JKISS32() { 
    int t; 

    y ^= (y<<5); y ^= (y>>7); y ^= (y<<22); 

    t = z+w+c; z = w; c = t < 0; w = t&2147483647; 

    x += 1411392427; 

    return x + y + w; 
}

Also there is one web site to test RNG http://www.phy.duke.edu/~rgb/General/dieharder.php