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

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.

Answer 2

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

Answer 3

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 4

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;
}

Answer 5

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

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