C Random Number Generation (pure C code, no libraries or functions)

Question

I need to generate some random numbers in C for testing and debugging the system. The system is a custom hardware (SoC) with a limited set of functions so I can only use basic mathematical operations.

And no, I can't use random number generators in stdlib or math.h. I need to write it myself. So is there some sort of algorithm for generating random numbers?

I know that a simple solution is to generate the numbers here on my workstation and embed them into the module, but I don't want to do that.

Answer 1

A random number generator is basically a special^* hash function which runs recursively from a starting seed.

I've used the MurmurHash2 algorithm in my C# code to good effect. It's extremely fast and simple to implement and has been tested to be very well distributed with low collision rates. The project has several different open source hash functions written in C++ which should be easily convertible to C.

---

^{* By special I mean that running the hash function on a value should return another seemingly random (but determinate) value, so that the output doesn't appear to form patterns. Also, the distribution of the returned value should have a uniform distribution.}

Answer 2

Just dig up the article by Park and Miller in the Oct 88 issue of CACM.

The general algorithm they propose is:

a = 16807;
m = 2147483647;
seed = (a * seed) mod m;
random = seed / m;

Though the article includes several refinements.

Answer 3

A linear congruential generator would be simple to implement. A nice implementation in pure C is available here.

Answer 4

You can try Multiply-with-carry by George Marsaglia.

Code from Wikipedia:

#include <stdint.h>

#define PHI 0x9e3779b9

static uint32_t Q[4096], c = 362436;

void init_rand(uint32_t x)
{
    int i;

    Q[0] = x;
    Q[1] = x + PHI;
    Q[2] = x + PHI + PHI;

    for (i = 3; i < 4096; i++)
            Q[i] = Q[i - 3] ^ Q[i - 2] ^ PHI ^ i;
}

uint32_t rand_cmwc(void)
{
    uint64_t t, a = 18782LL;
    static uint32_t i = 4095;
    uint32_t x, r = 0xfffffffe;
    i = (i + 1) & 4095;
    t = a * Q[i] + c;
    c = (t >> 32);
    x = t + c;
    if (x < c) {
            x++;
            c++;
    }
    return (Q[i] = r - x);
}

Answer 5

Check the source code of the gsl library, a couple of well tested algorithms are implemented in it.

Answer 6

You may want to look for Mersenne Twister. There are lots of algorithms of higher quality. A good article with an overview you find here:

http://en.wikipedia.org/wiki/Pseudorandom_number_generator

Answer 7

You might try Isaac which is also available as part of CCAN here