implementation of rand()

Question

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.

Answer 1

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.)

Answer 2

I found this: http://www.codeproject.com/KB/recipes/SimpleRNG.aspx.

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?

Answer 3

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

Answer 4

The standard solution is to use a linear feedback shift register

Answer 5

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.

Answer 6

Mersenne twister

A bit from Wikipedia:

• It was designed to have a period of 219937 − 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 219937 unique combinations (219937 is approximately 4.3 × 106001; this is many orders of magnitude larger than the estimated number of particles in the observable universe, which is 1080).
• 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.

Answer 7

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.

Answer 8

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.